Scattered packings of cycles

Publication date 1 September 2016

Abstract: We consider the problem Scattered Cycles which, given a graph

G

and two positive integers

r

and

e l l

, asks whether

G

contains a collection of

r

cycles that are pairwise at distance at least

e l l

. This problem generalizes the problem Disjoint Cycles which corresponds to the case

e l l = 1

. We prove that when parameterized by

r

,

e l l

, and the maximum degree

D e l t a

, the problem Scattered Cycles admits a kernel on

24 e l l^{2} D e l t a^{e} l l r l o g (8 e l l^{2} D e l t a^{e} l l r)

vertices. We also provide a

(16 e l l^{2} D e l t a^{e} l l)

-kernel for the case

r = 2

and a

(148 D e l t a r l o g r)

-kernel for the case

e l l = 1

. Our proofs rely on two simple reduction rules and a careful analysis.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Scattered packings of cycles