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

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 k^c(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)} + n^O(1) and a Monte Carlo algorithm of running time 2^O(√k) + n^O(1). For DOMINATING SET our results implies a significant simplification and refinement of a 2^O(√k) n^O(1) algorithm on H minor free graphs due to Demaine et al. [SODA 2003, J. ACM 2005].