A Cubic Kernel for Feedback Vertex Set and Loop Cutset |
| |
Authors: | Hans L Bodlaender Thomas C van Dijk |
| |
Affiliation: | (1) 84081 Baronissi, Salerno, (SA), Italy;(2) Dip. Mat. e Inform., Univ. Salerno, 32611 Gainesville, FL, USA;(3) Center for Applied Optim. Dept. Industrial and Systems Engin., Univ. Florida, 32611 Gainesville, FL, USA;(4) Information Sci. Res. AT&T Labs Res., Florham Park, Florham Park, 07932, NJ, USA |
| |
Abstract: | 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′≤k, 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|