Partial vs. Complete Domination: t-Dominating Set

摘要

We examine the parameterized complexity ot t-Dominating Set, the problem of finding a set of at most k nodes that dominate at least t nodes of a graph G = (V,E). The classic NP-complete problem Dominating Set, which can be seen to be t-Dominating Set with the restriction that t = n, has long been known to be W[2]-complete when parameterized in k. Whereas this implies W[2]-hardness for t-Dominating Set and the parameter k, we are able to prove fixed-parameter tractabil-ity for t-dominating Set and the parameter t. More precisely, we obtain a quintic problem kernel and a randomized O((4 + ε)~t poly(n)) algorithm. The algorithm is based on the divide-and-color method introduced to the community earlier this year, rather intuitive and can be derandomized using a standard framework.