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.