Graph partitioning using single commodity flows

ABSTRACT

We show that the sparsest cut in graphs with n vertices and m edges can be approximated within O(log² n) factor in Õ(m + n^3/2) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows that take time Õ(m + n²). Our algorithm iteratively employs max-flow computations to embed an expander flow, thus providing a certificate of expansion. Our technique can also be extended to yield an O(log² n)-(pseudo-) approximation algorithm for the edge-separator problem with a similar running time.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: Alon, N., and Milman, V. 1985. λ₁, isoperimetric inequalities for graphs, and superconcentrators. J. Combinat. Theory, Ser. B 38, 73--88.
• 3: Sanjeev Arora , Elad Hazan , Satyen Kale, 0(\sqrt {\log n)} Approximation to SPARSEST CUT in Õ(n²) Time, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.238-247, October 17-19, 2004 [doi>10.1109/FOCS.2004.1]
• 4: 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]
• 5: Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
• 6: Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
• 7: Ball, K. 1997. An elementary introduction to modern convex geometry. In Flavors of Geometry, S. Levy, Ed. Cambridge University Press, Cambridge, 1--58.
• 8: András A. Benczúr , David R. Karger, Approximating s-t minimum cuts in Õ(n²) time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.47-55, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237827]
• 9: Donath, W., and Hoffman, A. J. 1973. Lower bounds for partitioning of graphs. IBM J. Res. Develop. 17, 420--425.
• 10: Lisa K. Fleischer, Approximating Fractional Multicommodity Flow Independent of the Number of Commodities, SIAM Journal on Discrete Mathematics, v.13 n.4, p.505-520, Oct. 2000 to Nov. 2000 [doi>10.1137/S0895480199355754]
• 11: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 12: Andrew V. Goldberg , Satish Rao, Beyond the flow decomposition barrier, Journal of the ACM (JACM), v.45 n.5, p.783-797, Sept. 1998 [doi>10.1145/290179.290181]
• 13: Bruce Hendrickson , Robert Leland, An improved spectral graph partitioning algorithm for mapping parallel computations, SIAM Journal on Scientific Computing, v.16 n.2, p.452-469, March 1995 [doi>10.1137/0916028]
• 14: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual Design Automation Conference, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
• 15: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 16: Kernighan, B. W., and Lin, S. 1970. An efficient heuristic procedure for partitioning graphs. The Bell Systems Tech. J. 29, 2, 291--307.
• 17: Lang, K. 2005. Fixing two weaknesses of the spectral method. In Proceedings of the Neural Information Processing Systems.
• 18: Kevin Lang , Satish Rao, Finding near-optimal cuts: an empirical evaluation, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.212-221, January 25-27, 1993, Austin, Texas, United States
• 19: Lang, K., and Rao, S. 2004. A flow-based method for improving the expansion or conductance of graph cuts. In Proceedings of the MPS Conference on Integer Programming and Combinatorial Optimization. 325--337.
• 20: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 21: Linial, N., London, E., and Rabinovich, Y. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 2, 215--246.
• 22: R. Motwani, Expanding graphs and the average-case analysis of algorithms for matchings and related problems, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.550-561, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73060]
• 23: 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]
• 24: Alex Pothen , Horst D. Simon , Kan-Pu Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.430-452, Jul. 1990 [doi>10.1137/0611030]
• 25: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
• 26: 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]
• 27: Tanner, R. M. 1984. Explicit concentrators from generalized n-gons. SIAM J. Alg. Disc. Methods 5, 287--293.
• 28: Walshaw, C. 2000. The graph partitioning archive. http://staffweb.cms.gre.ac.uk/~wc06/partition/.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
Edge-separator, single commodity max-flow, sparse cut, spectral method