2008 · 106 citations · 18 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsDiscrete MathematicsApproximation AlgorithmsDirected Acyclic GraphsGraph AlgorithmsAlgorithmic Graph TheoryInapproximabilityNode OrderingRandomized Graph Algorithms
We prove that approximating the max. acyclic subgraph problem within a factor better than 1/2 is unique games hard. Specifically, for every constant epsiv > 0 the following holds: given a directed graph G that has an acyclic subgraph consisting of a fraction (1-epsiv) of its edges, if one can efficiently find an acyclic subgraph of G with more than (1/2 + epsiv) of its edges, then the UGC is false. Note that it is trivial to find an acyclic subgraph with 1/2 the edges, by taking either the forward or backward edges in an arbitrary ordering of the vertices of G. The existence of a rho-approximation algorithmfor rho > 1/2 has been a basic open problem for a while. Our result is the first tight inapproximability result for an ordering problem. The starting point of our reduction isa directed acyclic subgraph (DAG) in which every cut isnearly-balanced in the sense that the number of forward and backward edges crossing the cut are nearly equal; such DAGs were constructed by Charikar et al. Using this, we are able to study max. acyclic subgraph, which is a constraint satisfaction problem (CSP) over an unbounded domain, by relating it to a proxy CSP over a bounded domain. The latter is then amenable to powerful techniques based on the invariance principle. Our results also give a super-constant factor inapproximability result for the feedback arc set problem. Using our reductions, we also obtain SDP integrality gapsfor both the problems.
18
On the power of unique 2-prover 1-round games
Subhash Khot · 2002 · 854 citations
Subhash Khot, Oded Regev · Journal of Computer and System Sciences · 2007 · 761 citations
Optimal algorithms and inapproximability results for every CSP?
Prasad Raghavendra · 2008 · 408 citations
Approximating Minimum Feedback Sets and Multicuts in Directed Graphs
Guy Even, Joseph Naor, Baruch Schieber et al. · Algorithmica · 1998 · 313 citations