Advertisement
Published in:
2008 | OriginalPaper | Chapter
A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs
Authors : Hans L. Bodlaender, Eelko Penninkx, Richard B. Tan
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider the following problem: given a planar graph
G
= (
V
,
E
) and integer
k
, find if possible at least
k
vertex disjoint cycles in
G
. This problem is known to be NP-complete. In this paper, we give a number of simple data reduction rules. Each rule transforms the input to an equivalent smaller input, and can be carried out in polynomial time. We show that inputs on which no rule can be carried out have size linear in
k
. Thereby we obtain that the
k
-Disjoint Cycles
problem on planar graphs has a kernel of linear size. We also present a parameterized algorithm with a running time of
$O(c^{\sqrt{k}} + n^2)$
.