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.
Although there exists a simple @math -approximation algorithm for the vertex cover problem, there is strong evidence that approximating the problem with a factor of @math might be hard, for every @math @cite_10 . It should be noted that the feedback vertex set and diamond hitting set problems are at least as hard to approximate as the vertex cover problem, in the sense that the existence of a @math -approximation algorithm for one of these two problems implies the existence of a @math -approximation algorithm for the vertex cover problem, where @math is a constant.
@cite_10
2137118456
Based on a conjecture regarding the power of unique 2-prover-1-round games presented in [S. Khot, On the power of unique 2-Prover 1-Round games, in: Proc. 34th ACM Symp. on Theory of Computing, STOC, May 2002, pp. 767-775], we show that vertex cover is hard to approximate within any constant factor better than 2. We actually show a stronger result, namely, based on the same conjecture, vertex cover on k-uniform hypergraphs is hard to approximate within any constant factor better than k.