Scattered packings of cycles

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 par...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2016-09, Vol.647, p.33-42
Main Authors: Atminas, Aistis, Kamiński, Marcin, Raymond, Jean-Florent
Format: Article
Language:English
Subjects:
Collection
Computer Science
Cycle packing
Discrete Mathematics
Graphs
Induced structures
Integers
Kernelization
Kernels
Multivariate algorithms
Reduction
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2016.07.021