Theory of Computing
-------------------
Title : Hardness of Vertex Deletion and Project Scheduling
Authors : Ola Svensson
Volume : 9
Number : 24
Pages : 759-781
URL : http://www.theoryofcomputing.org/articles/v009a024
Abstract
--------
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).