Scattered packings of cycles

Aistis Atminas; Marcin Kamiński; Jean Florent Raymond

doi:10.1016/j.tcs.2016.07.021

Scattered packings of cycles

Aistis Atminas, Marcin Kamiński, Jean Florent Raymond^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

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ℓ²Δ^ℓrlog⁡(8ℓ²Δ^ℓr) vertices. We also provide a (16ℓ²Δ^ℓ)-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.

Original language	English
Pages (from-to)	33-42
Number of pages	10
Journal	Theoretical Computer Science
Volume	647
DOIs	https://doi.org/10.1016/j.tcs.2016.07.021
Publication status	Published - 27 Sept 2016
Externally published	Yes

Keywords

Cycle packing
Induced structures
Kernelization
Multivariate algorithms

Access to Document

10.1016/j.tcs.2016.07.021

Cite this

Atminas, A., Kamiński, M., & Raymond, J. F. (2016). Scattered packings of cycles. Theoretical Computer Science, 647, 33-42. https://doi.org/10.1016/j.tcs.2016.07.021

@article{cf436401556746489008e749d21d773d,

title = "Scattered packings of cycles",

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 = "Cycle packing, Induced structures, Kernelization, Multivariate algorithms",

author = "Aistis Atminas and Marcin Kami{\'n}ski and Raymond, {Jean Florent}",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier B.V.",

year = "2016",

month = sep,

day = "27",

doi = "10.1016/j.tcs.2016.07.021",

language = "English",

volume = "647",

pages = "33--42",

journal = "Theoretical Computer Science",

issn = "0304-3975",

}

TY - JOUR

T1 - Scattered packings of cycles

AU - Atminas, Aistis

AU - Kamiński, Marcin

AU - Raymond, Jean Florent

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Δrlog⁡r)-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Δrlog⁡r)-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 -

Scattered packings of cycles

Abstract

Keywords

Access to Document

Other files and links

Cite this