pith. sign in

arxiv: 1409.2733 · v4 · pith:QZHWX3OCnew · submitted 2014-09-09 · 💻 cs.DM · cs.DS· math.CO

Scattered packings of cycles

classification 💻 cs.DM cs.DSmath.CO
keywords cyclesdeltaproblemcasekernelscatteredadmitsanalysis
0
0 comments X
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.