Theory of Computing
-------------------
Title : Simple Proof of Hardness of Feedback Vertex Set
Authors : Venkatesan Guruswami and Euiwoong Lee
Volume : 12
Number : 6
Pages : 1-11
URL : http://www.theoryofcomputing.org/articles/v012a006
Abstract
--------
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 efficient constant-
factor approximation is ruled out under the Unique Games Conjecture
(UGC). We give a simpler proof that Feedback Vertex Set is hard to
approximate within any constant factor, assuming UGC.