A PRIMAL-DUAL INTERPRETATION OF 2 2-APPROXIMATION ALGORITHMS FOR THE FEEDBACK VERTEX SET PROBLEM IN UNDIRECTED GRAPHS

Recently, Becker and Geiger and Bafna, Berman and Fujito gave 2-approx imation algorithms for the feedback vertex set problem in undirected g raphs. We show how their algorithms can be explained in terms of the p rimal-dual method for approximation algorithms, which has been used to derive approximation algorithms for network design problems. In the p rocess, we give a new integer programming formulation for the feedback vertex set problem whose integrality gap is at worst a factor of two; the well-known cycle formulation has an integrality gap of Theta(log n), as shown by Even, Naor, Schieber and Zosin. We also give a new 2-a pproximation algorithm for the problem which is a simplification of th e Bafna et al. algorithm. (C) 1998 Elsevier Science B.V. All rights re served.