Abstract:

We give a subexponential-time approximation algorithm for the Unique > Games > problem: Given a Unique Games instance with optimal value 1-epsilon > and alphabet size k, our algorithm finds in time exp(k*n^beta) a > solution of value 1-sqrt(epsilon/beta^3). Here, beta>0 is a parameter > of the algorithm that can be chosen arbitrarily small. > > 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 interesting 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 results stop short of refuting the UGC, they do 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 guarantee. > > The main component in our algorithms is a new kind of graph > decomposition that may have other applications: We show that every > graph with n vertices can be efficiently partitioned into disjoint > induced subgraphs, each with at most n^beta eigenvalues above 1-eta, > such that at most a > sqrt(epsilon/beta^3) fraction of the edges of the graph does not > respect the partition. > > Joint work with Sanjeev Arora and Boaz Barak.