Amir Abboud, Weizmann Institute of Science

Abstract

The All-Pairs Max-Flow problem (APMF) asks to compute the maximum flow (or equivalently, the minimum cut) between all pairs of nodes in a graph. The naive solution of making n^2 calls to a (single-pair) max-flow algorithm was beaten in 1961 by a remarkable algorithm of Gomory and Hu that only makes n-1 calls. Within the same time bound, their algorithm also produces a cut-equivalent tree (a.k.a. GH-Tree) that preserves all pairwise minimum cuts exactly. This gives a cubic upper bound for APMF assuming that single-pair max-flow can be solved optimally, and the only improvements since 1961 have been on getting us closer to this assumption; new algorithms that break the cubic barrier were only known for special graph classes or with approximations.

The All-Pairs Shortest-Path problem (APSP) is similar but asks to compute the distance rather than the connectivity between all pairs of nodes. Its time complexity also appears similar, with classical cubic time algorithms that have only been broken in special cases or with approximations. Meanwhile, in the past 10 years, the conjecture that APSP requires cubic time has played a central role in fine-grained complexity, leading to cubic conditional lower bounds for many other fundamental problems that appear even easier than APMF. However, a formal reduction from APSP to APMF has remained elusive.

This talk will overview a sequence of recent works (based on joint works with Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, and Ohad Trabelsi) breaking the 60-year-old cubic barrier for APMF and suggesting a separation between APMF and APSP.

See: https://theory.cs.rutgers.edu/theory_seminar