Kernels for (Connected) dominating set on graphs with excluded topological minors

We give the first linear kernels for the Dominating Set and Connected Dominating Set problems on graphs excluding a fixed graph H as a topological minor. In other words, we prove the existence of polynomial time algorithms that, for a given H-topological-minor-free graph G and a positive integer k, output an Htopological-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 one. Our results extend the known classes of graphs on which the Dominating Set and Connected Dominating Set problems admit linear kernels. Prior to our work, it was known that these problems admit linear kernels on graphs excluding a fixed apex graph H as a minor. Moreover, for Dominating Set, a kernel of size k^c(H⁾, where c(H) is a constant depending on the size of H, follows from a more general result on the kernelization of Dominating Set on graphs of bounded degeneracy. Alon and Gutner explicitly asked whether one can obtain a linear kernel for Dominating Set on H-minor-free graphs. We answer this question in the affirmative and in fact prove a more general result. For Connected Dominating Set no polynomial kernel even on H-minor-free graphs was known prior to our work. On the negative side, it is known that Connected Dominating Set on 2-degenerated graphs does not admit a polynomial kernel unless coNP ⊆ NP/poly. Our kernelization algorithm is based on a non-trivial combination of the following ingredients • The structural theorem of Grohe and Marx [STOC 2012] for graphs excluding a fixed graph H as a topological minor; • A novel notion of protrusions, different than the one defined in [FOCS 2009]; • Our results are based on a generic reduction rule that produces an equivalent instance (in case the input graph is H-minor-free) of the problem, with treewidth O(k). The application of this rule in a divide-and-conquer fashion, together with the new notion of protrusions, gives us the linear kernels. A protrusion in a graph [FOCS 2009] is a subgraph of constant treewidth which is separated from the rest of the graph by at most a constant number of vertices. In our variant of protrusions, instead of stipulating that the subgraph be of constant treewidth, we ask that it contains a constant number of vertices from a solution. We believe that this new take on protrusions would be useful for other graph problems and in different algorithmic settings.