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       : https://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.