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.