A Linear Kernel for the fc-Disjoint Cycle Problem on Planar Graphs

摘要

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-DISOINT Cycles problem on planar graphs has a kernel of linear size. We also present a parameterized algorithm with a running time of O(c~(k~(1/2))+n~2).