Subexponential algorithms for unique games and related problems

with Sanjeev Arora, Boaz Barak. FOCS 2010, JACM.

Best Paper Award at FOCS 2010

abstract

We give a subexponential time approximation algorithm for the Unique Games problem: Given a Unique Games instance with optimal value $1-\varepsilon^6$ and alphabet size k, our algorithm finds in time $\exp(k n^\varepsilon)$ a solution of value $1-\varepsilon$ .

We also obtain subexponential algorithms with similar approximation guarantees for Small-Set Expansion and Multi Cut. For Max Cut, Sparsest Cut and Vertex Cover, our techniques lead to subexponential algorithms with improved approximation guarantees on subclasses of instances.

Khot's Unique Games Conjecture (UGC) states that it is NP-hard to achieve approximation guarantees such as ours for Unique Games. While our result stops short of refuting the UGC, it does suggest that Unique Games is significantly easier than NP-hard problems such as Max 3-SAT, Label Cover and more, that are believed not to have subexponential algorithms achieving a non-trivial approximation ratio.

The main component in our algorithms is a new kind of graph decomposition that may have other applications: We show that by changing an $\varepsilon$ fraction of its edges, any regular graph on n vertices can be broken into disjoint parts such that the stochastic adjacency matrix of each part has at most $n^\varepsilon$ eigenvalues larger than $1-\varepsilon^6$ .

keywords

small-set expansion
Unique Games Conjecture
eigenvalues
approximation algorithms