## 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