96-29: Constant Ratio Approximations of Feedback Vertex Sets in Weighted Undirected Graphs

DIMACS TR: 96-29

Constant Ratio Approximations of Feedback Vertex Sets in Weighted Undirected Graphs

Authors: Vineet Bafna, Piotr Berman and Toshihiro Fujito

ABSTRACT
A feedback vertex set of a graph is a subset of vertices that contains at least one vertex from every cycle in the graph. We show that a feedback vertex set approximating a minimum one within a constant factor can be efficiently found in undirected graphs. In fact the derived approximation ratio matches the best constant ratio known today for the vertex cover problem, improving the previous best results for both weighted and unweighted cases. The existence of an approximation preserving reduction of the vertex cover problem to the feedback vertex set problem suggests that further improvement of the obtained ratio will require entirely new ideas.

We extend our approach to handle graphs of bounded vertex degree, and show an improved performance ratio for this case. These approximation bounds are obtained by using a non--trivial generalization of the classical local ratio principle of Bar--Yehuda and Even.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-29.ps.gz

DIMACS Home Page