History

Please fill in your query. A complete syntax description you will find on the General Help page.
Partial vs. complete domination: $t$-Dominating Set. (English)
van Leeuwen, Jan (ed.) et al., SOFSEM 2007: Theory and practice of computer science. 33rd conference on current trends in theory and practice of computer science, Harrachov, Czech Republic, January 20‒26, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-69506-6/pbk). Lecture Notes in Computer Science 4362, 367-376 (2007).
Summary: We examine the parameterized complexity of $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 tractability for $t$-Dominating Set and the parameter $t$. More precisely, we obtain a quintic problem kernel and a randomized $O((4+ε)^t \text {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.