2012/06/15 by Ola Svensson, Svensson, Ola · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Optimization and Search Problems #cs.CC
paper · pdf · doi:10.48550/arxiv.1206.3408
18 pages, 1 figure
arxiv created 2012/06/15 · openalex publication_date 2012/06/15 · arxiv updated 2012/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Assuming the Unique Games Conjecture, we show strong inapproximability results for two natural vertex deletion problems on directed graphs: for any integer k≥ 2 and arbitrary small ε> 0, the Feedback Vertex Set problem and the DAG Vertex Deletion problem are inapproximable within a factor k-ε even on graphs where the vertices can be almost partitioned into k solutions. This gives a more structured and therefore stronger UGC-based hardness result for the Feedback Vertex Set problem that is also simpler (albeit using the "It Ain't Over Till It's Over" theorem) 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 NP-hard to approximate within any constant assuming the Unique Games Conjecture. This explains the difficulty in obtaining good approximation algorithms for that problem and further motivates previous alternative approaches such as bicriteria approximations.