Rohit Khandekar
Satish Rao
ABSTRACT
We 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 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.
- R. Ahuja, T. Magnati, and J. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Eaglewood Cliffs, NJ, 1993. Google Scholar
Digital Library
- N. Alon and V. Milman. λ1, isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory, Series B, 38:73--88, 1985.Google ScholarCross Ref
- S. Arora, E. Hazan, and S. Kale. O(√ log n) approximation to sparsest cut in Õ(n2) time. In Proceedings, IEEE Symposium on Foundations of Computer Science, pages 238--247, 2004. Google ScholarDigital Library
- S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings, and graph partitioning. In Proceedings, ACM Symposium on Theory of Computing, pages 222--231, 2004. Google ScholarDigital Library
- A. Benczúr and D. Karger. Approximating s-t minimum cuts in Õ(n2) time. In Proceedings, ACM Symposium on Theory of Computing, pages 47--55, 1996. Google ScholarDigital Library
- W. Donath and A. J. Hoffman. Lower bounds for partitioning of graphs. IBM J. Res. Develop., 17:420--425, 1973.Google ScholarDigital Library
- A. Goldberg and S. Rao. Beyond the flow decomposition barrier. J. ACM, 45:783--797, 1998. Google ScholarDigital Library
- B. Hendrickson and R. Leland. An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM J. Sci. Stat. Comput., 16(2):452--469, 1995. Google ScholarDigital Library
- G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multilevel hypergraph partitioning: Applications in VLSI design. In Proc. ACM/IEEE Design Automation Conference, pages 526--529, 1997. Google ScholarDigital Library
- G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20:359 -- 392, 1999. Google ScholarDigital Library
- B. Kernighan and S. Lin. An effective heuristic procedure for partitioning graphs. The Bell System Technical Journal, pages 291--308, 1970.Google ScholarCross Ref
- K. Lang. Finding good nearly balanced cuts in power law graphs. Manuscript, 2004.Google Scholar
- K. Lang and S. Rao. Finding near-optimal cuts: An empirical evaluation. In Symposimum on Discrete Algorithms, pages 212--221, 1993. Google ScholarDigital Library
- F. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787--832, 1999. Google ScholarDigital Library
- H. Simon, A. Pothen, and K. P. Liou. Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Mat. Theory and Appl., 11(3):430--452, 1990. Google ScholarDigital Library
- D. Spielman and S. Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings, ACM Symposium on Theory of Computing, pages 81--90, 2004. Google ScholarDigital Library
- R. Tanner. Explicit concentrators from generalized n-gons. SIAM J. Alg. Disc. Methods, 5:287--293, 1984.Google ScholarCross Ref
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 ...
Graph partitioning using single commodity flows
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 ...
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 ...
Comments