Scattered packings of cycles

作者：Atminas Aistis; Kaminski Marcin; Raymond Jean Florent^*

来源：Theoretical Computer Science, 2016, 647: 33-42.

DOI：10.1016/j.tcs.2016.07.021

• Cycle packing
• Kernelization
• Multivariate algorithms
• Induced structures

We consider the problem SCATTERED CYCLES which, given a graph G and two positive integers r and l, 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 l = 1. We prove that when parameterized by r, l, and the maximum degree Delta, the problem SCATTERED CYCLES admits a kernel on 24l(2)Delta(l)r log(8l(2)Delta(l)r) vertices. We also provide a (16l(2)Delta(l))-kernel for the case r = 2 and a (148 Delta rlogr)-kernel for the case l=1. Our proofs rely on two simple reduction rules and a careful analysis.

• 出版日期2016-9-27