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

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