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 inGaconnected dominating set of Gsuch 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.
kernelization connected dominating set girth fixed-parameter tractability kernel lower bounds