TY - GEN

T1 - Linear kernels for (connected) dominating set on H-minor-free graphs

AU - Fomin, Fedor V.

AU - Lokshtanov, Daniel

AU - Saurabh, Saket

AU - Thilikos, Dimitrios M.

PY - 2012

Y1 - 2012

N2 - We give the first linear kernels for DOMINATING SET and CONNECTED DOMINATING SET problems on graphs excluding a fixed graph H as a minor. In other words, we give polynomial time algorithms that, for a given H-minor free graph G and positive integer k, output an H-minor free graph G′ on O(k) vertices such that G has a (connected) dominating set of size k if and only if G′ has. Prior to our work, the only polynomial kernel for DOMINATING SET on graphs excluding a fixed graph H as a minor was due to Alon and Gutner [ECCC 2008, IWPEC 2009] and to Philip, Raman, and Sikdar [ESA 2009] but the size of their kernel is kc(H), where c(H) is a constant depending on the size of H. Alon and Gutner asked explicitly, whether one can obtain a linear kernel for DOMINATING SET on H-minor free graphs. We answer this question in affirmative. For CONNECTED DOMINATING SET no polynomial kernel on H-minor free graphs was known prior to our work. Our results are based on a novel generic reduction rule producing an equivalent instance of the problem with treewidth O(√k). The application of this rule in a divide-and-conquer fashion together with protrusion techniques brings us to linear kernels. As a byproduct of our results we obtain the first subexponential time algorithms for CONNECTED DOMINATING SET, a deterministic algorithm solving the problem on an n-vertex H-minor free graph in time 2O(√k log k) + nO(1) and a Monte Carlo algorithm of running time 2O(√k) + nO(1). For DOMINATING SET our results implies a significant simplification and refinement of a 2O(√k) nO(1) algorithm on H minor free graphs due to Demaine et al. [SODA 2003, J. ACM 2005].

AB - We give the first linear kernels for DOMINATING SET and CONNECTED DOMINATING SET problems on graphs excluding a fixed graph H as a minor. In other words, we give polynomial time algorithms that, for a given H-minor free graph G and positive integer k, output an H-minor free graph G′ on O(k) vertices such that G has a (connected) dominating set of size k if and only if G′ has. Prior to our work, the only polynomial kernel for DOMINATING SET on graphs excluding a fixed graph H as a minor was due to Alon and Gutner [ECCC 2008, IWPEC 2009] and to Philip, Raman, and Sikdar [ESA 2009] but the size of their kernel is kc(H), where c(H) is a constant depending on the size of H. Alon and Gutner asked explicitly, whether one can obtain a linear kernel for DOMINATING SET on H-minor free graphs. We answer this question in affirmative. For CONNECTED DOMINATING SET no polynomial kernel on H-minor free graphs was known prior to our work. Our results are based on a novel generic reduction rule producing an equivalent instance of the problem with treewidth O(√k). The application of this rule in a divide-and-conquer fashion together with protrusion techniques brings us to linear kernels. As a byproduct of our results we obtain the first subexponential time algorithms for CONNECTED DOMINATING SET, a deterministic algorithm solving the problem on an n-vertex H-minor free graph in time 2O(√k log k) + nO(1) and a Monte Carlo algorithm of running time 2O(√k) + nO(1). For DOMINATING SET our results implies a significant simplification and refinement of a 2O(√k) nO(1) algorithm on H minor free graphs due to Demaine et al. [SODA 2003, J. ACM 2005].

KW - Algorithmic graph minors

KW - Connected dominating set

KW - Dominating set

KW - Kernelization

KW - Parameterized complexity

UR - http://www.scopus.com/inward/record.url?scp=84860115094&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84860115094&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973099.7

DO - 10.1137/1.9781611973099.7

M3 - Conference contribution

AN - SCOPUS:84860115094

SN - 9781611972108

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 82

EP - 93

BT - Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

PB - Association for Computing Machinery

T2 - 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

Y2 - 17 January 2012 through 19 January 2012

ER -