Scattered packings of cycles

Abstract

We consider the problem Scattered Cycles which, given a graph $G$ and two positive integers $r$ and $\ell$, asks whether $G$ contains a collection of $r$ cycles that are pairwise at distance at least $\ell$. This problem generalizes the problem Disjoint Cycles which corresponds to the case $\ell =1$. We prove that when parameterized by $r$, $\ell$, and the maximum degree $\Delta$, the problem Scattered Cycles admits a kernel on $24{\ell }^2{\Delta }^{\ell }r\log (8{\ell }^2{\Delta }^{\ell }r)$ vertices. We also provide a $(16{\ell }^2{\Delta }^{\ell })$-kernel for the case $r=2$ and a $(148\Delta r\log r)$-kernel for the case $\ell =1$. Our proofs rely on two simple reduction rules and a careful analysis.

17 pages