TY - JOUR
T1 - Scattered packings of cycles
AU - Atminas, Aistis
AU - Kamiński, Marcin
AU - Raymond, Jean Florent
N1 - Publisher Copyright:
© 2016 Elsevier B.V.
PY - 2016/9/27
Y1 - 2016/9/27
N2 - 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Δrlogr)-kernel for the case ℓ=1. Our proofs rely on two simple reduction rules and a careful analysis.
AB - 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Δrlogr)-kernel for the case ℓ=1. Our proofs rely on two simple reduction rules and a careful analysis.
KW - Cycle packing
KW - Induced structures
KW - Kernelization
KW - Multivariate algorithms
UR - http://www.scopus.com/inward/record.url?scp=84995563320&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2016.07.021
DO - 10.1016/j.tcs.2016.07.021
M3 - Article
AN - SCOPUS:84995563320
SN - 0304-3975
VL - 647
SP - 33
EP - 42
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -