The effect of girth on the kernelization complexity of Connected Dominating Set

Neeldhara Misra, Geevarghese Philip, Venkatesh Raman & Saket Saurabh
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...