Get all the updates for this publication

Conferences

Beating the random ordering is hard: inapproximability of maximum acyclic subgraphPublished in

2008

DOI: 10.1109/FOCS.2008.51

Pages: 573 - 582

We prove that approximating the MAX ACYCLIC SUBGRAPH problem within a factor better than 1/2 is Unique Games hard. Specifically, for every constant ε > 0 the following holds: given a directed graph G that has an acyclic subgraph consisting of a fraction (1 - ε) of its edges, if one can efficiently find an acyclic subgraph of G with more than (1/2 + ε) 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 p-approximation algorithm for ρ > 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 is a directed acyclic subgraph (DAG) in which every cut is nearly-balanced in the sense that the number of forward and backward edges crossing the cut are nearly equal; such DAGs were constructed in [2]. 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 [12,17]. Our results also give a super-constant factor inapproximability result for the MIN FEEDBACK ARC SET problem. Using our reductions, we also obtain SDP integrality gaps for both the problems. © 2008 IEEE.

Topics: Induced subgraph isomorphism problem (67)%67% related to the paper, Subgraph isomorphism problem (65)%65% related to the paper, Feedback arc set (60)%60% related to the paper, Unique games conjecture (54)%54% related to the paper and Directed graph (53)%53% related to the paper

View more info for "Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph"

Content may be subject to copyright.

About the journal

Journal | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

ISSN | 02725428 |