Inapproximability of Feedback Vertex Set for Bounded Length Cycles.
Venkatesan Guruswami, Euiwoong Lee · Electronic colloquium on computational complexity · 2014
The Feedback Vertex Set problem (FVS), where the goal is to find a small subset of ver- tices that intersects every cycle in an input directed graph, is among the fundamental prob- lems whose approximability is not well-understood. One can efficiently find an O(log n) factor approximation, but the best NP-hardness result is only a factor of ≈ 1.36 (via a sim- ple 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 bounded length. For this variant, we prove strong NP-hardness of approximation results: For any integer constant k > 3 and > 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 k′ > k where k′ can be taken to be Ω( logn log logn ). Taking k′ = ω(log n log logn) would be enough to prove a hardness for FVS (for arbitrary length cycles). Our work thus identifies the problem of hitting cycles of length ≈ log n as the key towards resolving the approximability of FVS. Our result is based on reductions from k-uniform Hypergraph Vertex Cover with ran- dom 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 re- sult for finding a minimum-sized set of 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). ∗Supported in part by NSF grant CCF-1115525. [email protected] †Supported by a Samsung Fellowship, US-Israel BSF grant 2008293, and NSF CCF-1115525. [email protected] ISSN 1433-8092 Electronic Colloquium on Computational Complexity, Revision 1 of Report No. 6 (2014)