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

Abstract

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 G[S] 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 W[2]-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.