Subexponential Algorithms for Unique Games and Related Problems

Abstract

Subexponential time approximation algorithms are presented for the Unique Games and Small-Set Expansion problems. Specifically, for some absolute constant c, the following two algorithms are presented.

(1) An exp(kn^ϵ)-time algorithm that, given as input a k-alphabet unique game on n variables that has an assignment satisfying 1-ϵ^c fraction of its constraints, outputs an assignment satisfying 1-ϵ fraction of the constraints.

(2) An exp(n^ϵ/δ)-time algorithm that, given as input an n-vertex regular graph that has a set S of δn vertices with edge expansion at most ϵ^c, outputs a set S' of at most δ n vertices with edge expansion at most ϵ.

subexponential algorithm is also presented with improved approximation to Max Cut, Sparsest Cut, and Vertex Cover on some interesting subclasses of instances. These instances are graphs with low threshold rank, an interesting new graph parameter highlighted by this work.

Khot's Unique Games Conjecture (UGC) states that it is NP-hard to achieve approximation guarantees such as ours for Unique Games. While the results here stop short of refuting the UGC, they do suggest that Unique Games are significantly easier than NP-hard problems such as Max 3-Sat, Max 3-Lin, Label Cover, and more, which are believed not to have a subexponential algorithm achieving a nontrivial approximation ratio.

Of special interest in these algorithms is a new notion of graph decomposition that may have other applications. Namely, it is shown for every ϵ >0 and every regular n-vertex graph G, by changing at most δ fraction of G's edges, one can break G into disjoint parts so that the stochastic adjacency matrix of the induced graph on each part has at most n^ϵ eigenvalues larger than 1-η, where η depends polynomially on ϵ. The subexponential algorithm combines this decomposition with previous algorithms for Unique Games on graphs with few large eigenvalues [Kolla and Tulsiani 2007; Kolla 2010].

References

1. Noga Alon. 1986. Eigenvalues and expanders. Combinatorica 6, 2 (1986), 83--96.
2. Noga Alon and Bo‚az Klartag. 2009. Economical toric spines via Cheeger's inequality. J. Topol. Anal. 1, 2 (2009), 101--111.
3. Noga Alon and Vitaly Milman. 1985. λ₁, isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory Ser. B 38, 1 (1985), 73--88. DOI:http://dx.doi.org/10.1016/0095-8956(85)90092-9
4. Sanjeev Arora, Russell Impagliazzo, William Matthews, and David Steurer. 2010. Improved Algorithms for Unique Games via Divide and Conquer. Technical Report ECCC TR10-041. Electronic Colloquium on Computational Complexity.
5. Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth Vishnoi. 2008. Unique games on expanding constraints graphs are easy. In Proceedings of the 40th STOC. ACM.
6. Per Austrin. 2007. Towards sharp inapproximability for any 2-CSP. In Proceedings of the FOCS. 307--317.
7. Boaz Barak, Parikshit Gopalan, Johan Håastad, Raghu Meka, Prasad Raghavendra, and David Steurer. 2012. Making the long code shorter. In Proceedings of the IEEE FOCS. 370--379.
8. Boaz Barak, Moritz Hardt, Thomas Holenstein, and David Steurer. 2011a. Subsampling mathematical relaxations and average-case complexity. In Proceedings of the ACM-SIAM SODA.
9. Boaz Barak, Prasad Raghavendra, and David Steurer. 2011b. Rounding semidefinite programming hierarchies via global correlation. In Proceedings of the IEEE FOCS.
10. A. Bulatov, P. Jeavons, and A. Krokhin. 2005. Classifying the complexity of constraints using finite algebras. SIAM J. Comput 34, 3 (2005), 720--742.
11. Moses Charikar, Konstantin Makarychev, and Yury Makarychev. 2006. Near-optimal algorithms for unique games. In Proceedings of STOC. 205--214.
12. Shuchi Chawla, Robi Krauthgamer, Ravi Kumar, Yuval Rabani, and D. Sivakumar. 2006. On the hardness of approximating multicut and sparsest-cut. Comput. Complex. 15, 2 (2006), 94--114.
13. C. Chekuri and M. Pal. 2005. A recursive greedy algorithm for walks in directed graphs. In Proceedings of the IEEE FOCS. 245--253.
14. Eden Chlamtac, Konstantin Makarychev, and Yury Makarychev. 2006. How to play unique games using embeddings. In Proceedings of the 47th FOCS. 687--696.
15. Fan Chung. 2007. Random walks and local cuts in graphs. Linear Algebra Appl. 423, 1 (2007), 22--32.
16. Ted Dimitriou and Russell Impagliazzo. 1998. Go with the winners for graph bisection. In Proceedings of the 9th SODA. 510--520.
17. U. Feige and D. Reichman. 2004. On systems of linear equations with two variables per equation. In Proceedings of RANDOM-APPROX. 117--127.
18. Alan M. Frieze and Ravi Kannan. 1999. Quick approximation to matrices and applications. Combinatorica 19, 2 (1999), 175--220.
19. Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. 2004. Multiway cuts in node weighted graphs. J. Algorithms 50, 1 (2004), 49--61.
20. Sharad Goel, Ravi Montenegro, and Prasad Tetali. 2006. Mixing time bounds via the spectral profile. Electron. J. Probab. 11, 1 (2006), 1--26.
21. Anupam Gupta, Robert Krauthgamer, and James R. Lee. 2003. Bounded geometries, fractals, and low-distortion embeddings. In Proceedings of the FOCS. 534--543.
22. Anupam Gupta and Kunal Talwar. 2006. Approximating unique games. In Proceedings of the 17th SODA. ACM, 106.
23. Venkatesan Guruswami, Rajsekar Manokaran, and Prasad Raghavendra. 2008. Beating the random ordering is hard: Inapproximability of maximum acyclic subgraph. In Proceedings of the FOCS. 573--582.
24. Venkatesan Guruswami and Ali Kemal Sinop. 2011. Lasserre hierarchy, higher eigenvalues, and approximation schemes for quadratic integer programming with PSD objectives. In Proceedings of the IEEE FOCS.
25. Eran Halperin and Robi Krauthgamer. 2003. Polylogarithmic inapproximability. In Proceedings of the STOC. ACM, 594.
26. Johan Håastad. 2001. Some optimal inapproximability results. J. ACM 48, 4 (2001), 798--859.
27. R. Impagliazzo, R. Paturi, and F. Zane. 2001. Which problems have strongly exponential complexity? J. Comput. System Sci. 63, 4 (2001), 512--530.
28. Subhash Khot. 2002. On the power of unique 2-prover 1-round games. In Proceedings of the 34th STOC. ACM Press, New York, 767--775.
29. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. 2007. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput. 37, 1 (2007), 319--357.
30. Subhash Khot and Oded Regev. 2008. Vertex cover might be hard to approximate to within 2-ε. J. Comput. Syst. Sci. 74, 3 (2008), 335--349.
31. Subhash Khot and Rishi Saket. 2009. SDP Integrality gaps with local ℓ₁-embeddability. In Proceedings of the FOCS. 565--574.
32. Subhash Khot and Nisheeth K. Vishnoi. 2005. The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into ℓ₁. In Proceedings of the FOCS. 53--62.
33. Alexandra Kolla. 2010. Spectral algorithms for unique games. In Proceedings of the IEEE Conference on Computational Complexity. 122--130.
34. Alexandra Kolla and Madhur Tulsiani. 2007. Playing random and expanding unique games. Unpublished manuscript available from the authors' webpages. Subsumed by {Arora et al. 2008}.
35. Gabor Kun and Mario Szegedy. 2009. A new line of attack on the dichotomy conjecture. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing. ACM New York, NY, USA, 725--734.
36. James R. Lee, Shayan Oveis Gharan, and Luca Trevisan. 2014. Multiway spectral partitioning and higher-order cheeger inequalities. J. ACM 61, 6 (2014), 37. http://dx.doi.org/10.1145/2665063
37. A. K. Lenstra and H. W. Jr. Lenstra. 1993. The Development of the Number Field Sieve. Springer-Verlag, Berlin.
38. Nathan Linial and Michael E. Saks. 1993. Low diameter graph decompositions. Combinatorica 13, 4 (1993), 441--454.
39. Anand Louis, Prasad Raghavendra, Prasad Tetali, and Santosh Vempala. 2012. Many sparse cuts via higher eigenvalues. In Proceedings of the 44th Symposium on Theory of Computing Conference (STOC'12). 1131--1140. DOI:http://dx.doi.org/10.1145/2213977.2214079
40. Eugene M. Luks. 1982. Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci. 25, 1 (1982), 42--65.
41. Rajsekar Manokaran, Joseph Naor, Prasad Raghavendra, and Roy Schwartz. 2008. SDP gaps and UGC hardness for multiway cut, 0-extension, and metric labeling. In Proceedings of the STOC. 11--20.
42. Dana Moshkovitz and Ran Raz. 2008. Two query PCP with sub-constant error. In Proceedings of the 49th FOCS. 314--323.
43. E. Mossel, R. O'Donnell, and K. Oleszkiewicz. 2008. Noise stability of functions with low influences: Invariance and optimality. Ann. Math. 101 (2008).
44. Assaf Naor. 2004. On the Banach space valued Azuma inequality and small set isoperimetry in Alon-Roichman graphs. Available as eprint http://arxiv.org/abs/1009.5695v1arXiv:1009.5695v1.
45. Assaf Naor. 2012. On the Banach-space-valued azuma inequality and small-set isoperimetry of Alon-Roichman graphs. Combinatorics Probab. Comput. 21, 4 (2012), 623--634. DOI:http://dx.doi.org/10.1017/S0963548311000757
46. C. H. Papadimitriou and M. Yannakakis. 1991. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43, 3 (1991), 425--440.
47. Prasad Raghavendra. 2008. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the 40th STOC. ACM, 245--254.
48. Prasad Raghavendra and David Steurer. 2009. Integrality gaps for strong SDP relaxations of unique games. In Proceedings of the FOCS. 575--585.
49. Prasad Raghavendra and David Steurer. 2010. Graph expansion and the unique games conjecture. In Proceedings of the STOC. 755--764.
50. Prasad Raghavendra, David Steurer, and Prasad Tetali. 2010. Approximations for the isoperimetric and spectral profile of graphs and related parameters. In Proceedings of the STOC. ACM.
51. Prasad Raghavendra, David Steurer, and Madhur Tulsiani. 2012. Reductions between expansion problems. In Proceedings of the IEEE Conference on Computational Complexity.
52. R. E. Stearns and H. B. Hunt III. 1990. Power indices and easier hard problems. Math. Syst. Theory 23, 4 (1990), 209--225.
53. David Steurer. 2010a. Fast SDP algorithms for constraint satisfaction problems. In Proceedings of the SODA. 684--697.
54. David Steurer. 2010b. On the Complexity of Unique Games and Graph Expansion. Technical Report TR-887-10. Princeton University. ftp://ftp.cs.princeton.edu/techreports/2010/887.pdf.
55. David Steurer. 2010c. Subexponential algorithms for d-to-1 two-prover games and for certifying almost perfect expansion. Manuscript, available from the author's website. http://www.cs.cornell.edu/∼dsteurer/.
56. David Steurer. 2014. Subexponential approximations for multicut. Manuscript, available from the author's website. http://www.cs.cornell.edu/∼dsteurer/.
57. David Steurer and Nisheeth Vishnoi. 2009. Connections between unique games and multicut. Technical Report TR09-125. Electronic Colloquium on Computational Complexity.
58. E. Szemerédi. 1976. Regular partitions of graphs. Problèmes combinatoires et théorie des graphes, Orsay (1976).
59. Luca Trevisan. 2005. Approximation algorithms for unique games. In Proceedings of the FOCS. 197--205.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

• Theory of computation

  • Computational complexity and cryptography

    • Complexity classes

  • Design and analysis of algorithms