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 $\widetilde{O}(\log n)$ factor approximation, but the best NP-hardness result is only a factor of $\approx 1.36$ (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 $k \ge 3$ and $\epsilon > 0$, it is hard to find a $(k-1-\epsilon)$-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 $k' \ge k$ where $k'$ can be taken to be $\Omega(\frac{\log n}{\log \log n})$. Taking $k' = \omega(\log n \log \log n)$ would be enough to prove a hardness for FVS (for arbitrary length cycles). Our work thus identifies the problem of hitting cycles of length $\approx \log n$ 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-\epsilon)$ 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 $\Omega(k)$ hardness result for finding a minimum-sized set of {\em edges} to hit all $k$-cycles. We also obtain almost tight $\widetilde{\Omega}(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 $\widetilde{\Omega}(\sqrt{k})$ NP-hardness result).

Added a simpler proof of the inapproximability of FVS based on the UGC

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 $\widetilde{O}(\log n)$ factor approximation, and while a constant-factor approximation is ruled out under the Unique Games Conjecture (UGC), the best NP-hardness result is only a factor of about 1.36 (via a simple reduction from Vertex Cover).

This work studies a natural variant of the Feedback Vertex Set problem (FVS), where the goal is to find a small subset of vertices that intersects every cycle of *bounded length*. For this variant, we prove strong *NP-hardness* of approximation results: For any integer constant $k \ge 3$ and $\epsilon > 0$, it is hard to find a $(k-1-\epsilon)$-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 $k' \ge k$ where $k'$ can be taken to be $\Omega(\frac{\log n}{\log \log n})$. Taking $k' = \omega(\log n \log \log n)$ would be enough to prove a hardness for FVS (for arbitrary length cycles). Our work thus identifies the problem of hitting cycles of length $\approx \log n$ 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-\epsilon)$ 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 $\Omega(k)$ hardness result for finding a minimum-sized set of *edges* to hit all $k$-cycles. We also obtain almost tight $\widetilde{\Omega}(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 $\widetilde{\Omega}(\sqrt{k})$ NP-hardness result).