The 3-Cycle Transversal problem (covering all triangles) was studied by Krivelevich [Discrete Mathematics, 1995], where an LP-based 2-approximation algorithm was presented. The integrality gap of the underlying LP was posed as an open problem in the work of Krivelevich. We resolve this problem by showing a sequence of graphs with integrality gap approaching 2. In addition, we show that if 3-Cycle Transversal admits a (2 − ε)-approximation algorithm, then so does the Vertex-Cover problem, and thus improving the ratio 2 is unlikely. We also show that k -Cycle Transversal admits a (k − 1)-approximation algorithm, which extends the result of Krivelevich from k = 3 to any k. Based on this, for odd k we give an algorithm for k -Cycle-Free Subgraph with ratio \frack-12k-3=\frac12+\frac14k-6\frac{k-1}{2k-3}=\frac{1}{2}+\frac{1}{4k-6} ; this improves over the trivial ratio of 1/2.

Our main result however is for the k -Cycle-Free Subgraph problem with even values of k. For any k = 2r, we give an W(n^{-\frac1r+\frac1r(2r-1)-e})\Omega\left(n^{-\frac{1}{r}+\frac{1}{r(2r-1)}-\varepsilon}\right) -approximation scheme with running time ε ^{− Ω(1/ε)} poly(n). This improves over the ratio Ω(n ^− 1/r ) that can be deduced from extremal graph theory. In particular, for k = 4 the improvement is from Ω(n ^− 1/2) to Ω(1/n ^{− 1/3 − ε} ).

Similar results are shown for the problem of covering cycles of length ≤ k or finding a maximum subgraph without cycles of length ≤ k.