Subexponential algorithms for unique games and related problems

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

PDF

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ε61-\varepsilon^6 and alphabet size k, our algorithm finds in time exp(knε)\exp(k n^\varepsilon) a solution of value 1ε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εn^\varepsilon eigenvalues larger than 1ε61-\varepsilon^6.

keywords

  • small-set expansion
  • Unique Games Conjecture
  • eigenvalues
  • approximation algorithms