All-Pairs Min-Cut vs. All-Pairs Shortest-Path - Amir Abboud

Computer Science/Discrete Mathematics Seminar I
10:30am|Simonyi 101 and Remote Access
Topic: All-Pairs Min-Cut vs. All-Pairs Shortest-Path
Speaker: Amir Abboud
Affiliation: Weizmann Institute of Science
Date: January 20, 2026

The All-Pairs Min-Cut problem (APMC) asks to compute the minimum cut (or equivalently, the maximum flow) between all pairs of nodes in a graph.1 The naive solution of making n^2 calls to a single-pair min-cut algorithm was surpassed in 1961 by a remarkable algorithm of Gomory and Hu that requires only n-1 calls. Within the same time bound, their algorithm produces a cut-equivalent tree (or GH-Tree) that preserves all pairwise minimum cuts exactly.2 This yields a cubic upper bound for APMC, which has stood as the barrier for the general problem for over 60 years.

The All-Pairs Shortest-Path problem (APSP) appears similar, asking to compute the distance rather than the connectivity between all pairs. Its complexity landscape also seems analogous: despite the existence of mildly subcubic algorithms, a truly subcubic solution remains elusive. In fact, in the past 10 years, the conjecture that APSP requires essentially cubic time has played a central role in fine-grained complexity, leading to conditional lower bounds for many other fundamental problems that appear even easier than APMC. However, a formal reduction from APSP to APMC has remained elusive.

This talk will overview a sequence of works (with Krauthgamer, Li, Panigrahi, Saranurak, and Trabelsi) breaking the 60-year-old cubic barrier for APMC, establishing a counter-intuitive separation between APMC and APSP, and inspiring new attacks on the APSP conjecture. Along the way, we will highlight the use of techniques such as expander decompositions, regularity lemmas, and theorems from additive combinatorics.