Given an n-vertex digraph D = (V, A) the Max-k-Ordering problem is to compute a labeling @math maximizing the number of forward edges, i.e. edges (u,v) such that @math (u) 0 @math @math n^ (1 k ) @math S_v Z ^+ @math 4 2 ( 2 +1) 2.344 @math 2 2 2.828 @math k [n]$.
For the vertex deletion version of , @cite_10 gave linear time and quadratic time algorithms for rooted trees and series-parallel graphs respectively. The problem reduces to vertex cover on @math -uniform hypergraphs for any constant @math thereby admitting a @math -approximation, and a matching @math -inapproximability assuming the UGC was obtained by Svensson @cite_3 .
@cite_10 @cite_3
2079297844 2950822364
Examines the vertex deletion problem for weighted directed acyclic graphs (WDAGs). The objective is to delete the fewest number of vertices so that the resulting WDAG has no path of length > spl delta . Several simplified versions of this problem are shown to be NP-hard. However, the problem is solved in linear time when the WDAG is a rooted tree, and in quadratic time when the WDAG is a series-parallel graph. > Assuming the Unique Games Conjecture, we show strong inapproximability results for two natural vertex deletion problems on directed graphs: for any integer @math and arbitrary small @math , the Feedback Vertex Set problem and the DAG Vertex Deletion problem are inapproximable within a factor @math even on graphs where the vertices can be almost partitioned into @math 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.