A Cubic Kernel for Feedback Vertex Set and Loop Cutset

作者：Bodlaender Hans L^*; van Dijk Thomas C

来源：Theory of Computing Systems, 2010, 46(3): 566-597.

DOI：10.1007/s00224-009-9234-2

• Graphs
• Algorithms
• Kernelization algorithms
• Preprocessing
• Data reduction
• Feedback vertex set
• Loop cutset
• Polynomial kernels
• Fixed parameter tractability

The Feedback Vertex Set problem on unweighted, undirected graphs is considered. Improving upon a result by Burrage et al. (Proceedings 2nd International Workshop on Parameterized and Exact Computation, pp. 192-202, 2006), we show that this problem has a kernel with O(k (3)) vertices, i.e., there is a polynomial time algorithm, that given a graph G and an integer k, finds a graph G' with O(k (3)) vertices and integer k'a parts per thousand currency signk, such that G has a feedback vertex set of size at most k, if and only if G' has a feedback vertex set of size at most k'. Moreover, the algorithm can be made constructive: if the reduced instance G' has a feedback vertex set of size k', then we can easily transform a minimum size feedback vertex set of G' into a minimum size feedback vertex set of G. This kernelization algorithm can be used as the first step of an FPT algorithm for Feedback Vertex Set, but also as a preprocessing heuristic for Feedback Vertex Set.
We also show that the related Loop Cutset problem also has a kernel of cubic size. The kernelization algorithms are experimentally evaluated, and we report on these experiments.

• 出版日期2010-4