Max cut and the smallest eigenvalue

ABSTRACT

We describe a new approximation algorithm for Max Cut. Our algorithm runs in ~O(n²) time, where n is the number of vertices, and achieves an approximation ratio of .531. On instances in which an optimal solution cuts a 1-ε fraction of edges, our algorithm finds a solution that cuts a 1-4√ε + 8ε-o(1) fraction of edges. Our main result is a variant of spectral partitioning, which can be implemented in nearly linear time. Given a graph in which the Max Cut optimum is a 1-ε fraction of edges, our spectral partitioning algorithm finds a set S of vertices and a bipartition L,R=S-L of S such that at least a 1-O(√ε) fraction of the edges incident on S have one endpoint in L and one endpoint in R. (This can be seen as an analog of Cheeger's inequality for the smallest eigenvalue of the adjacency matrix of a graph.) Iterating this procedure yields the approximation results stated above. A different, more complicated, variant of spectral partitioning leads to a polynomial time algorithm that cuts a 1/2 + e^-Ω(1/ε) fraction of edges in graphs in which the optimum is 1/2 + ε.

REFERENCES

• 1: Amit Agarwal , Moses Charikar , Konstantin Makarychev , Yury Makarychev, O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060675]
• 2: N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
• 3: Noga Alon , Assaf Naor, Approximating the Cut-Norm via Grothendieck's Inequality, SIAM Journal on Computing, v.35 n.4, p.787-803, 2006 [doi>10.1137/S0097539704441629]
• 4: Noga Alon , Benny Sudakov, Bipartite Subgraphs and the Smallest Eigenvalue, Combinatorics, Probability and Computing, v.9 n.1, p.1-12, January 2000 [doi>10.1017/S0963548399004071]
• 5: Sanjeev Arora , Satyen Kale, A combinatorial, primal-dual approach to semidefinite programs, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250823]
• 6: S. Arora, S. Rao, and U. Vazirani. Expander flows and a √log n-approximation to sparsest cut. In Proceedings of the 36th ACM Symposium on Theory of Computing, 2004.
• 7: Yonatan Bilu , Nathan Linial, Lifts, Discrepancy and Nearly Optimal Spectral Gap, Combinatorica, v.26 n.5, p.495-519, October 2006 [doi>10.1007/s00493-006-0029-7]
• 8: Moses Charikar , Anthony Wirth, Maximizing Quadratic Programs: Extending Grothendieck's Inequality, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.54-60, October 17-19, 2004 [doi>10.1109/FOCS.2004.39]
• 9: Wenceslas Fernandez de la Vega , Claire Kenyon-Mathieu, Linear programming relaxations of maxcut, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.53-61, January 07-09, 2007, New Orleans, Louisiana
• 10: Charles Delorme , Svatopluk Poljak, Combinatorial properties and complexity of a max-cut approximation, European Journal of Combinatorics, v.14 n.4, p.313-333, July 1993 [doi>10.1006/eujc.1993.1035]
• 11: C. Delorme , S. Poljak, Laplacian eigenvalues and the maximum cut problem, Mathematical Programming: Series A and B, v.62 n.3, p.557-574, Dec. 8, 1993 [doi>10.1007/BF01585184]
• 12: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 13: W. Haemers. Eigenvalue techniques in design and graph theory. PhD thesis, Eindhoven University of Technology, 1979.
• 14: Rohit Khandekar , Satish Rao , Umesh Vazirani, Graph partitioning using single commodity flows, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132574]
• 15: Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510017]
• 16: Subhash Khot , Guy Kindler , Elchanan Mossel , Ryan O'Donnell, Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.146-154, October 17-19, 2004 [doi>10.1109/FOCS.2004.49]
• 17: Subhash Khot , Ryan O'Donnell, SDP gaps and UGC-hardness for MAXCUTGAIN, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.217-226, October 21-24, 2006 [doi>10.1109/FOCS.2006.67]
• 18: J. Kuczyński , H. Woźniakowski, Estimating the largest eigenvalues by the power and Lanczos algorithms with a random start, SIAM Journal on Matrix Analysis and Applications, v.13 n.4, p.1094-1122, Oct. 1992 [doi>10.1137/0613066]
• 19: L. Lovász. Semidefinite programs and combinatorial optimization. In B. Reed and C. Linhares-Sales, editors, Recent Advances in Algorithms and Combinatorics, pages 137--194. Springer, 2003.
• 20: Elchanan Mossel , Ryan O'Donnell , Krzysztof Oleszkiewicz, Noise stability of functions with low in.uences invariance and optimality, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.21-30, October 23-25, 2005 [doi>10.1109/SFCS.2005.53]
• 21: Ryan O'Donnell , Yi Wu, An optimal sdp algorithm for max-cut, and equally optimal long code tests, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374425]
• 22: Lorenzo Orecchia , Leonard J. Schulman , Umesh V. Vazirani , Nisheeth K. Vishnoi, On partitioning graphs via single commodity flows, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374442]
• 23: G. Ottaviano and L. Trevisan. An experimental analysis of a spectral approximation algorithm for MAX CUT. Preprint, 2008.
• 24: Grant Schoenebeck , Luca Trevisan , Madhur Tulsiani, Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250836]
• 25: Daniel A. Spielman , Shang-Hua Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007372]
• 26: Luca Trevisan, Non-approximability results for optimization problems on bounded degree instances, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.453-461, July 2001, Hersonissos, Greece [doi>10.1145/380752.380839]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms

Keywords:
maximum cut, spectral partitioning