05508819

a

05508819 Chen, Jianer Fomin, Fedor V. Liu, Yang Lu, Songjian Villanger, Yngve Improved algorithms for the feedback vertex set problems. Dehne, Frank (ed.) et al., Algorithms and data structures. 10th international workshop, WADS 2007, Halifax, Canada, August 15--17, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73948-7/pbk). Lecture Notes in Computer Science 4619, 422-433 (2007). 2007 Berlin: Springer EN

doi:10.1007/978-3-540-73951-7_37

Summary: We present improved parameterized algorithms for the Feedback Vertex Set problem on both unweighted and weighted graphs. Both algorithms run in time $O(5^{k } k n ^{2})$. The algorithms construct a feedback vertex set of size bounded by $k$ (in the weighted case this set is of minimum weight among the feedback vertex set of size at most $k)$ in a given graph $G$, or reports that no such a feedback vertex set exists in $G$.