Revised: May 4, 2013
Published: September 26, 2013
Abstract: [Plain Text Version]
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.
In comparison to the classical Feedback Vertex Set problem, the DAG Vertex Deletion problem has received little attention and, although we think it is a natural and interesting problem, the main motivation for our inapproximability result stems from its relationship with the classical Discrete Time-Cost Tradeoff Problem. More specifically, our results imply that the deadline version is UG-hard to approximate within any constant. This explains the difficulty in obtaining good approximation algorithms for that problem and further motivates previous alternative approaches such as bicriteria approximations.
An extended abstract of this paper appeared in the Proceedings of the 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2012 (APPROX'12).
Licensed under a Creative Commons Attribution License (CC-BY)