# APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time

Preprint · Amir Abboud, Robert Krauthgamer, Ohad Trabelsi

- Archive id: arxiv:2106.02981
- Published: 2021-06-05
- arXiv: https://arxiv.org/abs/2106.02981
- Source URL: https://arxiv.org/abs/2106.02981
- PDF: https://arxiv.org/pdf/2106.02981
- Provenance: arxiv

## Abstract

We design an $n^{2+o(1)}$-time algorithm that constructs a cut-equivalent (Gomory-Hu) tree of a simple graph on $n$ nodes. This bound is almost-optimal in terms of $n$, and it improves on the recent $\\tilde{O}(n^{2.5})$ bound by the authors (STOC 2021), which was the first to break the cubic barrier. Consequently, the All-Pairs Maximum-Flow (APMF) problem has time complexity $n^{2+o(1)}$, and for the first time in history, this problem can be solved faster than All-Pairs Shortest Paths (APSP). We further observe that an almost-linear time algorithm (in terms of the number of edges $m$) is not possible without first obtaining a subcubic algorithm for multigraphs. Finally, we derandomize our algorithm, obtaining the first subcubic deterministic algorithm for Gomory-Hu Tree in simple graphs, showing that randomness is not necessary for beating the $n-1$ times max-flow bound from 1961. The upper bound is $\\tilde{O}(n^{2\\frac{2}{3}})$ and it would improve to $n^{2+o(1)}$ if there is a deterministic single-pair maximum-flow algorithm that is almost-linear. The key novelty is in using a \`\`dynamic pivot'' technique instead of the randomized pivot selection that was central in recent works.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.