Given a directed acyclic graph, it is easy to "topological sort" its
vertices so all directed edges go forward in the ordering. But what
if there is some noise and the graph is only nearly acyclic, say 1%
of the edges need to be removed to make it acyclic. In this case, it
was not known how to efficiently find an ordering of the vertices
where even 51% of the edges go forward. (It is trivial to get half
the edges going forward by picking a random ordering, or taking
either the forward or backward edges in an arbitrary ordering.)

We prove that finding such an ordering is Unique-Games hard.
Specifically, for any constant eps > 0, given a directed graph G that
has an acyclic subgraph consisting of a fraction (1-eps) of its
edges, finding an acyclic subgraph of G with more than (1/2+\eps) of
its edges is Unique-Games hard. This is the first tight hardness of
approximation result for an ordering problem. Our result implies a
super-constant factor inapproximability result (under the UGC) for
the Feedback Arc Set problem.

Our proof uses two main ingredients: a directed acyclic graph
constructed by Charikar, Makarychev, and Makarychev which looks
"pseudorandom" (in terms of near equal forward/backward edges) at
every "scale"; and Raghavendra's reduction to convert integrality
gaps for CSPs into matching UG-hardness results.

Joint work with Rajsekar Manokaran and Prasad Raghavendra