Volume 12 (2016) Article 6 pp. 1-11 [Note]

Simple Proof of Hardness of Feedback Vertex Set

by Venkatesan Guruswami and Euiwoong Lee

Received: June 3, 2015
Revised: February 7, 2016
Published: August 2, 2016

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.

DOI: 10.4086/toc.2016.v012a006

© 2016 Venkatesan Guruswami and Euiwoong Lee
Licensed under a Creative Commons Attribution License (CC-BY)