The Feedback Vertex Set problem (FVS), where the goal is to find a small subset of vertices that intersects every cycle in an input directed graph, is among the fundamental problems whose approximability is not well-understood. One can efficiently find an O(logn) factor approximation, but the best NP-hardness result is only a factor of 136 (via a simple reduction from Vertex Cover). A constant-factor approximation is ruled out under the Unique Games Conjecture (UGC), and we give a simpler proof of this in the paper.

Our main result concerns a natural variant of FVS, where the goal is to find a small subset of vertices that intersects every cycle of {\em bounded length}. For this variant, we prove strong {\em NP-hardness} of approximation results: For any integer constant k3 and 0">0, it is hard to find a (k−1−)-approximate solution to the problem of intersecting every cycle of length at most k. The hardness result almost matches the trivial factor k approximation algorithm for the problem. In fact, the hardness holds also for the problem of hitting every cycle of length at most a parameter kk where k can be taken to be (lognloglogn). Taking k=(lognloglogn) would be enough to prove a hardness for FVS (for arbitrary length cycles). Our work thus identifies the problem of hitting cycles of length logn as the key towards resolving the approximability of FVS.

Our result is based on reductions from k-uniform Hypergraph Vertex Cover with random matching and labeling techniques. As byproducts of our techniques, we also prove a factor (k−1−) hardness of approximation result for k-Clique Transversal, where one must hit every k-clique in the graph with fewest possible vertices, and a factor (k) hardness result for finding a minimum-sized set of {\em edges} to hit all k-cycles. We also obtain almost tight (k) factor hardness results for the dual problem of packing vertex-disjoint k-cycles and k-cliques in a graph, albeit relying on the UGC for k-Cycle Packing (but we do get a weaker factor (k) NP-hardness result).