Scattered packings of cycles
classification
💻 cs.DM
cs.DSmath.CO
keywords
cyclesdeltaproblemcasekernelscatteredadmitsanalysis
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.