The Kernelization Complexity of Connected Domination in Graphs with (no) Small Cycles

In the Parameterized Connected Dominating Set problem the input consists of a graph G and a positive integer k, and the question is whether there is a set S of at most k vertices in G—a connected dominating set of G—such that (i) S is a dominating set of G, and (ii) the subgraph GS] induced by S is connected; the parameter is k. The underlying decision problem is a basic connectivity problem which is long known to be NP-complete, and it has been extensively studied using several algorithmic approaches. Parameterized Connected Dominating Set is W2]-hard, and therefore it is unlikely (Downey and Fellows, Parameterized Complexity, Springer, 1999) that the problem has fixed-parameter tractable (FPT) algorithms or polynomial kernels in graphs in general. We investigate the effect of excluding short cycles, as subgraphs, on the kernelization complexity of Parameterized Connected Dominating Set. The girth of a graph G is the length of a shortest cycle in G. It turns out that the Parameterized Connected Dominating Set problem is hard on graphs with small cycles, and becomes progressively easier as the girth increases. More precisely, we obtain the following kernelization landscape: Parameterized Connected Dominating Set

• does not have a kernel of any size on graphs of girth three or four (since the problem is W2]-hard);
• admits a kernel of size 2 ^k k ^3k on graphs of girth at least five;
• has no polynomial kernel (unless the Polynomial Hierarchy collapses to the third level) on graphs of girth at most six, and,
• has a cubic ( $\mathcal {O}(k^{3})$ ) vertex kernel on graphs of girth at least seven.

While there is a large and growing collection of parameterized complexity results available for problems on graph classes characterized by excluded minors, our results add to the very few known in the field for graph classes characterized by excluded subgraphs.