Item

Abstract

In the Connected Dominating Set problem we are given as input a graph G and a positive integer k, and are asked if there is a set S of at most k vertices of G such that S is a dominating set of G and the subgraph induced by S is connected. This is a basic connectivity problem that is known to be NP-complete, and it has been extensively studied using several algorithmic approaches. In this paper we study the effect of excluding short cycles, as a subgraph, on the \em kernelization complexity} of Connected Dominating Set. Kernelization algorithms are polynomial-time algorithms that take an input and a positive integer k (the {\em parameter}) and output an equivalent instance where the size of the new instance and the new parameter are both bounded by some function g(k). The new instance is called a g(k) {\em kernel} for the problem. If g(k) is a polynomial in k then we say that the problem admits polynomial kernels. The girth of a graph G is the length of a shortest cycle in G. It turns out that Connected Dominating Set is ``hard'' on graphs with small cycles, and becomes progressively easier as the girth increases. More specifically, we obtain the following interesting trichotomy: Connected Dominating Set \begin{itemize} \item does not have a kernel of {\em any} size on graphs of girth 3 or 4 (since the problem is W[2]-hard); \item admits a g(k) kernel, where g(k) is k^{O(k)}, on graphs of girth 5 or 6 but has {\em no} polynomial kernel (unless the Polynomial Hierarchy (PH) collapses to the third level) on these graphs; \item has a cubic (O(k^3)) kernel on graphs of girth at least 7. \end{itemize} While there is a large and growing collection of parameterized complexity results available for problems on graph classes characterized by excluded {\em minors}, our results add to the very few known in the field for graph classes characterized by excluded {\em subgraphs.