zbMATH — the first resource for mathematics

Hardness of vertex deletion and project scheduling. (English) Zbl 1366.68083
Summary: 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.

MSC:
 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 68R10 Graph theory (including graph drawing) in computer science 68W25 Approximation algorithms
Full Text: