Beating the random ordering is hard
Oct 21, 2009
Given a directed acyclic graph, it is easy to "topological sort" its
vertices such that all directed edges go forward in the ordering. But
what if the graph is only nearly acyclic, say 1% of the edges need to
be removed to make it acyclic? Is there a "robust" version of
topological sort that orders vertices of such a graph so that most of
the edges point forward?
It has been shown recently (G.-Manokaran-Raghavendra, FOCS'08) that
such an algorithm probably doesn't exist. Formally, for any constant
eps > 0, given a directed graph G that has an acyclic subgraph
consisting of a (1-eps) fraction of its edges, finding an acyclic
subgraph of G with more than (1/2+eps) of its edges is at least as
hard as refuting the Unique Games conjecture. This shows that it is
hard to beat the mindless algorithm that simply picks a random
ordering and gets 1/2 the edges going forward in expectation.
In the talk, I will describe the Unique Games framework for showing
hardness of approximation results via suitable "dictatorship tests". I
will then explain some details of how this framework can be adapted to
show the above hardness for Maximum Acyclic Subgraph. I might also
briefly discuss more general ordering constraint satisfaction
problems, and the phenomenon of "approximation resistance" where it
becomes hard to do better than simply picking a random solution.