A 2-approximation algorithm for the undirected feedback vertex set problem

A feedback vertex set of a graph is a subset of vertices that contains at l east one vertex from every cycle in the graph. The problem considered is th at of finding a minimum feedback vertex set given a weighted and undirected graph. We present a simple and efficient approximation algorithm with perf ormance ratio of at most 2, improving previous best bounds for either weigh ted or unweighted cases of the problem. Any further improvement on this bou nd, matching the best constant factor known for the vertex cover problem, i s deemed challenging. The approximation principle, underlying the algorithm, is based on a genera lized form of the classical local ratio theorem, originally developed for a pproximation of the vertex cover problem, and a more flexible style of its application.