We consider the following NP-hard problem: in a weighted graph, find a minimum cost set of vertices whose removal leaves a graph in which no two cycles share an edge. We obtain a constant-factor approximation algorithm, based on the primal-dual method. Moreover, we show that the integrality gap of the natural LP relaxation of the problem is ( n), where n denotes the number of vertices in the graph.
A better formulation has been introduced by @cite_5 . For @math , denote by @math the set of the edges of @math having both ends in @math , by @math the subgraph of @math induced by @math , and by @math the degree of @math in @math . Then, the following is a formulation for the feedback vertex set problem: @cite_5 showed that the integrality gap of this integer program asymptotically equals @math . Constraints ) derive from the simple observation that the removal of a feedback vertex set @math from @math generates a forest having at most @math edges. Notice that the covering inequalities ) are implied by ).
@cite_5
1990800802
Recently, Becker and Geiger and Bafna, Berman and Fujito gave 2-approximation algorithms for the feedback vertex set problem in undirected graphs. We show how their algorithms can be explained in terms of the primal-dual method for approximation algorithms, which has been used to derive approximation algorithms for network design problems. In the process, 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 @Q(logn), as shown by Even, Naor, Schieber and Zosin. We also give a new 2-approximation algorithm for the problem which is a simplification of the algorithm.