Volume 9 (2013) Article 24 pp. 759-781
APPROX-RANDOM 2012 Special Issue
Hardness of Vertex Deletion and Project Scheduling
Revised: May 4, 2013
Published: September 26, 2013
Assuming the Unique Games Conjecture, we show strong inapproximability results for two natural vertex deletion problems on directed graphs: for any integer $k\geq 2$ and arbitrary small $\epsilon > 0$, the Feedback Vertex Set problem and the DAG Vertex Deletion problem are inapproximable within a factor $k-\epsilon$ even on graphs where the vertices can be almost partitioned into $k$ solutions. This gives a more structured and yet simpler (albeit using the “It Ain't Over Till It's Over” theorem) UG-hardness result for the Feedback Vertex Set problem than the previous hardness result.