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

Simple Proof of Hardness of Feedback Vertex Set

Received: June 3, 2015

Revised: February 7, 2016

Published: August 2, 2016

Revised: February 7, 2016

Published: August 2, 2016

**Keywords:**inapproximability, UG-hardness, Feedback Vertex Set

**Categories:**complexity theory, algorithms, inapproximability, UG-hardness, Feedback Vertex Set, note

**ACM Classification:**F.2.2 (Nonnumerical Algorithms and Problems)

**AMS Classification:**68W25 (Approximation algorithms)

**Abstract:**
[Plain Text Version]

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.