Skip to main content

All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time

Publication ,  Conference
Abboud, A; Li, J; Panigrahi, D; Saranurak, T
Published in: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
January 1, 2023

A Gomory-Hu tree (also called a cut tree) succinctly represents (s, t) min-cuts (and therefore, (s, t) max-flow values) of all pairs of vertices s, t in an undirected graph. In this paper, we give an m1+o(1)-time algorithm for constructing a Gomory-Hu tree for a graph with m edges. This shows that the all-pairs max-flows problem has the same running time as the single-pair max-flow problem, up to a subpolynomial factor. Prior to our work, the best known Gomory-Hu tree algorithm was obtained in recent work by Abboud et al. (FOCS 2022) and requires Õ(n2) time for a graph with n vertices. Our result marks a natural culmination of over 60 years of research into the all-pairs maxflows problem that started with Gomory and Hu's pathbreaking result introducing the Gomory-Hu tree in 1961.

Duke Scholars

Published In

Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

DOI

ISSN

0272-5428

Publication Date

January 1, 2023

Start / End Page

2204 / 2212
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Abboud, A., Li, J., Panigrahi, D., & Saranurak, T. (2023). All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS (pp. 2204–2212). https://doi.org/10.1109/FOCS57990.2023.00137
Abboud, A., J. Li, D. Panigrahi, and T. Saranurak. “All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time.” In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2204–12, 2023. https://doi.org/10.1109/FOCS57990.2023.00137.
Abboud A, Li J, Panigrahi D, Saranurak T. All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time. In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. 2023. p. 2204–12.
Abboud, A., et al. “All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time.” Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2023, pp. 2204–12. Scopus, doi:10.1109/FOCS57990.2023.00137.
Abboud A, Li J, Panigrahi D, Saranurak T. All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. 2023. p. 2204–2212.

Published In

Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

DOI

ISSN

0272-5428

Publication Date

January 1, 2023

Start / End Page

2204 / 2212