pdf icon
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
Download article from ToC site:
[PDF (240K)]    [PS (944K)]    [PS.GZ (269K)]
[Source ZIP]
Keywords: inapproximability, UG-hardness, Feedback Vertex Set
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.