BIU theory seminar- May 3 : Amir Abboud - APMF < APSP? Gomory-Hu Tree in Subcubic Time
Arnold Filtser
Title: APMF < APSP? Gomory-Hu Tree in Subcubic Time
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-Paths 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 survey recent progress (based on joint works with Robert Krauthgamer and Ohad Trabelsi), starting with partially successful attempts at reducing APSP to APMF, going through algorithmic progress on APMF in limited settings, and leading up to a very recent paper (also with Jason Li, Debmalya Panigrahi, and Thatchaphol Saranurak) where we break the 60-year old cubic barrier for APMF; suggesting a separation between APMF and APSP.