Induced packings of cycles.
Aistis Atminas, Marcin Kamiński, Jean‐Florent Raymond · arXiv (Cornell University) · 2014
Two cycles of a graph are mutually induced if there is no edge between them in the graph. Given a graph $G$ and an integer $r,$ the problem Induced-Cycles asks whether $G$ contains a packing of $r$ pairwise mutually induced cycles. A reduction from Disjoint-Cycles shows that this problem has no polynomial kernel when parameterized by $r,$ unless $\mathrm{NP} \subseteq \mathrm{coNP}/\mathrm{poly},$ according to the results in [Bodlaender, Thomass\'e, Yeo, 2012]. In this paper, we show that the problem Induced-Cycles parameterized by the $r$ and the maximum degree $\Delta$ has an $O(\Delta^2)$-kernel for $r=2$ and an $O(r\Delta^2 \log(r\Delta))$-kernel for~$r>2.$ As a consequence, the problem Disjoint-Cycles also has a polynomial kernel for the same parameters.