Hardness of Vertex Deletion and Project Scheduling

Ola Svensson

Assuming the Unique Games Conjecture, we show strong inapproximability results for two natural vertex deletion problems on directed graphs: for any integer $k\ge 2$ and arbitrary…