Article

Graph partitioning using single commodity flows

Authors:

Rohit Khandekar,

Umesh VaziraniAuthors Info & Claims

STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

Pages 385 - 390

https://doi.org/10.1145/1132516.1132574

Published: 21 May 2006 Publication History

Abstract

We show that the sparsest cut in graphs can be approximated within O(log² n) factor in Õ(n^3/2) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows which take time Õ(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]

R. Ahuja, T. Magnati, and J. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Eaglewood Cliffs, NJ, 1993.

Digital Library

[2]

N. Alon and V. Milman. λ1, isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory, Series B, 38:73--88, 1985.

[3]

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.

Digital Library

[4]

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.

Digital Library

[5]

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.

Digital Library

[6]

W. Donath and A. J. Hoffman. Lower bounds for partitioning of graphs. IBM J. Res. Develop., 17:420--425, 1973.

Digital Library

[7]

A. Goldberg and S. Rao. Beyond the flow decomposition barrier. J. ACM, 45:783--797, 1998.

Digital Library

[8]

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.

Digital Library

[9]

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.

Digital Library

[10]

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.

Digital Library

[11]

B. Kernighan and S. Lin. An effective heuristic procedure for partitioning graphs. The Bell System Technical Journal, pages 291--308, 1970.

[12]

K. Lang. Finding good nearly balanced cuts in power law graphs. Manuscript, 2004.

[13]

K. Lang and S. Rao. Finding near-optimal cuts: An empirical evaluation. In Symposimum on Discrete Algorithms, pages 212--221, 1993.

Digital Library

[14]

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.

Digital Library

[15]

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.

Digital Library

[16]

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.

Digital Library

[17]

R. Tanner. Explicit concentrators from generalized n-gons. SIAM J. Alg. Disc. Methods, 5:287--293, 1984.

Cited By

Bernstein ABlikstad JSaranurak TTu T(2024)Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00123(2056-2077)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00123
Brand JChen LKyng RLiu YPeng RGutenberg MSachdeva SSidford A(2023)A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00037(503-514)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00037
Pyrgelis ATroncoso CDe Cristofaro E(2020)Measuring Membership Privacy on Aggregate Location Time-SeriesProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/33921544:2(1-28)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3392154
Show More Cited By

Index Terms

Graph partitioning using single commodity flows
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

On partitioning graphs via single commodity flows
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

In 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(log² n) factor in Õ(m + n^3/2) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows that ...
(Almost) Tight bounds and existence theorems for single-commodity confluent flows

A flow of a commodity is said to be confluent if at any node all the flow of the commodity leaves along a single edge. In this article, we study single-commodity confluent flow problems, where we need to route given node demands to a single destination ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

May 2006

786 pages

ISBN:1595931341

DOI:10.1145/1132516

Program Chair:
Jon Kleinberg
Cornell University, Ithaca, NY

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 May 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC06

Sponsor:

STOC06: Symposium on Theory of Computing

May 21 - 23, 2006

WA, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

71
Total Citations
View Citations
862
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bernstein ABlikstad JSaranurak TTu T(2024)Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00123(2056-2077)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00123
Brand JChen LKyng RLiu YPeng RGutenberg MSachdeva SSidford A(2023)A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00037(503-514)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00037
Pyrgelis ATroncoso CDe Cristofaro E(2020)Measuring Membership Privacy on Aggregate Location Time-SeriesProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/33921544:2(1-28)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3392154
Mehrotra R(2019)Inferring User Needs & Tasks from User InteractionsACM SIGIR Forum10.1145/3308774.330880652:2(176-177)Online publication date: 17-Jan-2019
https://dl.acm.org/doi/10.1145/3308774.3308806
Maistro M(2019)Exploiting User Signals and Stochastic Models to Improve Information Retrieval Systems and EvaluationACM SIGIR Forum10.1145/3308774.330880552:2(174-175)Online publication date: 17-Jan-2019
https://dl.acm.org/doi/10.1145/3308774.3308805
Lipani A(2019)On Biases in Information Retrieval Models and EvaluationACM SIGIR Forum10.1145/3308774.330880452:2(172-173)Online publication date: 17-Jan-2019
https://dl.acm.org/doi/10.1145/3308774.3308804
Järvelin K(2019)Salton Award KeynoteACM SIGIR Forum10.1145/3308774.330878252:2(52-63)Online publication date: 17-Jan-2019
https://dl.acm.org/doi/10.1145/3308774.3308782
Kyng RPachocki JPeng RSachdeva SKlein P(2017)A framework for analyzing resparsification algorithmsProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039818(2032-2043)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039818
Herrmann CZiegler M(2016)Computational Complexity of Quantum SatisfiabilityJournal of the ACM10.1145/286907363:2(1-31)Online publication date: 4-May-2016
https://dl.acm.org/doi/10.1145/2869073
Razborov A(2016)A New Kind of Tradeoffs in Propositional Proof ComplexityJournal of the ACM10.1145/285879063:2(1-14)Online publication date: 7-Apr-2016
https://dl.acm.org/doi/10.1145/2858790
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten