Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952471 | Theoretical Computer Science | 2016 | 10 Pages |
Abstract
We consider the problem Scattered Cycles which, given a graph G and two positive integers r and â, asks whether G contains a collection of r cycles that are pairwise at distance at least â. This problem generalizes the problem Disjoint Cycles which corresponds to the case â=1. We prove that when parameterized by r, â, and the maximum degree Î, the problem Scattered Cycles admits a kernel on 24â2Îârlogâ¡(8â2Îâr) vertices. We also provide a (16â2Îâ)-kernel for the case r=2 and a (148Îrlogâ¡r)-kernel for the case â=1. Our proofs rely on two simple reduction rules and a careful analysis.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Aistis Atminas, Marcin KamiÅski, Jean-Florent Raymond,