Rohit Khandekar
Satish Rao
Skip Abstract Section
Abstract
We show that the sparsest cut in graphs with n vertices and m edges can be approximated within O(log2 n) factor in Õ(m + n3/2) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows that take time Õ(m + n2). 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(log2 n)-(pseudo-) approximation algorithm for the edge-separator problem with a similar running time.
- Ahuja, R., Magnati, T., and Orlin, J. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Eaglewood Cliffs. Google Scholar
Digital Library
- Alon, N., and Milman, V. 1985. λ1, isoperimetric inequalities for graphs, and superconcentrators. J. Combinat. Theory, Ser. B 38, 73--88.Google ScholarCross Ref
- Arora, S., Hazan, E., and Kale, S. 2004a. O(&sqrt;log n) approximation to sparsest cut in Õ(n2) time. In Proceedings, IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, 238--247. Google ScholarDigital Library
- Arora, S., and Kale, S. 2007. A combinatorial, primal-dual approach to semidefinite programs. In Proceedings, ACM Symposium on Theory of Computing. 227--236. Google ScholarDigital Library
- Arora, S., Rao, S., and Vazirani, U. 2004b. Expander flows, geometric embeddings, and graph partitioning. In Proceedings, ACM Symposium on Theory of Computing. ACM, New York, 222--231. Google ScholarDigital Library
- Aumann, Y., and Rabani, Y. 1998. An O(log k) approximate max-flow min-cut theorem and approximation algorithm for multi-commodity flows. SIAM J. Comput. 27, 1, 291--301. Google ScholarDigital Library
- Ball, K. 1997. An elementary introduction to modern convex geometry. In Flavors of Geometry, S. Levy, Ed. Cambridge University Press, Cambridge, 1--58.Google Scholar
- Benczúr, A., and Karger, D. 1996. Approximating s-t minimum cuts in Õ(n2) time. In Proceedings of the ACM Symposium on Theory of Computing. ACM, New York, 47--55. Google ScholarDigital Library
- Donath, W., and Hoffman, A. J. 1973. Lower bounds for partitioning of graphs. IBM J. Res. Develop. 17, 420--425.Google ScholarDigital Library
- Fleischer, L. 2000. Approximating fractional multicommodity flow independent of the number of commodities. SIAM J. Discrete Math. 13, 505--520. Google ScholarDigital Library
- Garg, N., and Könemann, J. 1998. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, 300--309. Google ScholarDigital Library
- Goldberg, A., and Rao, S. 1998. Beyond the flow decomposition barrier. J. ACM 45, 783--797. Google ScholarDigital Library
- Hendrickson, B., and Leland, R. 1995. An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM J. Sci. Stat. Comput. 16, 2, 452--469. Google ScholarDigital Library
- Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. 1997. Multi-level hypergraph partitioning: Applications in VLSI design. In Proceedings of the ACM/IEEE Design Automation Conference. ACM, New York, 526--529. Google ScholarDigital Library
- Karypis, G., and Kumar, V. 1999. A fast and high quality multi-level scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing 20, 359--392. Google ScholarDigital Library
- Kernighan, B. W., and Lin, S. 1970. An efficient heuristic procedure for partitioning graphs. The Bell Systems Tech. J. 29, 2, 291--307.Google ScholarCross Ref
- Lang, K. 2005. Fixing two weaknesses of the spectral method. In Proceedings of the Neural Information Processing Systems.Google Scholar
- Lang, K., and Rao, S. 1993. Finding near-optimal cuts: An empirical evaluation. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 212--221. Google ScholarDigital Library
- 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.Google Scholar
- Leighton, F., and Rao, S. 1999. Multi-commodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46, 6, 787--832. Google ScholarDigital Library
- Linial, N., London, E., and Rabinovich, Y. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 2, 215--246.Google ScholarCross Ref
- Motwani, R. 1989. Expanding graphs and the average-case analysis of algorithms for matchings and related problems. In Proceedings of the ACM Symposium on Theory of Computing. ACM, New York, 550--561. Google ScholarDigital Library
- Orecchia, L., Schulman, L., Vazirani, U. V., and Vishnoi, N. K. 2008. On partitioning graphs via single commodity flows. In Proceedings of the ACM Symposium on Theory of Computing. ACM, New York, 461--470. Google ScholarDigital Library
- Simon, H., Pothen, A., and Liou, K. P. 1990. Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Math. Theory Appl. 11, 3, 430--452. Google ScholarDigital Library
- Sleator, D. D., and Tarjan, R. E. 1983. A data structure for dynamic trees. J. Comput. System Sci. 26, 3, 362--391. Google ScholarDigital Library
- Spielman, D., and Teng, S. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the ACM Symposium on Theory of Computing. ACM, New York, 81--90. Google ScholarDigital Library
- Tanner, R. M. 1984. Explicit concentrators from generalized n-gons. SIAM J. Alg. Disc. Methods 5, 287--293.Google ScholarCross Ref
- Walshaw, C. 2000. The graph partitioning archive. http://staffweb.cms.gre.ac.uk/~wc06/partition/.Google Scholar
Index Terms
- Graph partitioning using single commodity flows
Recommendations
On partitioning graphs via single commodity flows
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingIn this paper we obtain improved upper and lower bounds for the best approximation factor for Sparsest Cut achievable in the cut-matching game framework proposed in Khandekar et al. [9]. We show that this simple framework can be used to design ...
Expander flows, geometric embeddings and graph partitioning
We give a O(√log n)-approximation algorithm for the sparsest cut, edge expansion, balanced separator, and graph conductance problems. This improves the O(log n)-approximation of Leighton and Rao (1988). We use a well-known semidefinite relaxation with ...
Graph partitioning using single commodity flows
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of ComputingWe show that the sparsest cut in graphs can be approximated within O(log2 n) factor in Õ(n3/2) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows which take time Õ(n2). Our algorithm ...
Comments