arXiv preprint ·
Beyond Gomory-Hu: All-Pairs $\times$ All-Pairs Mincuts in $O(n)$ Space
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
For over four decades, two classical structures have offered complementary views of mincuts. The Gomory-Hu tree encodes one $(x,y)$-mincut for every vertex pair $x,y$ in $O(n)$ space, but retains only one mincut per pair. In contrast, for a fixed pair $x,y$, the Picard-Queyranne representation admits an $O(n)$ space vertex ordering that determines whether some $(x,y)$-mincut separates any given pair $u,v$ and reports such a cut. Can these complementary guarantees hold simultaneously in $O(n)$ space? We answer affirmatively. For undirected graphs, we construct an $O(n)$ space structure encoding, for every four vertices $x,y,u,v$, an $(x,y)$-mincut separating $u,v$ whenever one exists. More precisely, given any terminal pair $x,y$, the structure recovers the Picard-Queyranne ordering in $O(n)$ time. Thereafter, separability queries take $O(1)$ time, and reporting a separating mincut $C$ takes $O(|C|)$ time. Thus, information for all $Θ(n^4)$ choices of $x,y,u,v$ is encoded in $O(n)$ space. This is essentially the strongest information of this form that fits in $O(n)$ space: if one additionally requires the mincut to place $u$ on side of $x$ and $v$ on side of $y$, then $Ω(n^2)$ space is necessary even for fixed $x,y$. As a consequence, we obtain an $O(n)$ space all-pairs mincut sensitivity oracle for a single edge failure in multigraphs, with optimal $O(n)$ time to report a new mincut. This resolves an open question of Baswana and Pandey [SODA'22] on achieving $o(n^2)$ space and $o(m)$ query time simultaneously. Our construction substantially generalizes the $O(n)$ space nearest-mincut-hierarchy [SODA'27], which reports only the nearest $(x,y)$-mincut. Recovering the entire Picard-Queyranne ordering for an arbitrary pair requires new structural properties of the Dinitz-Vainshtein [STOC'94] connectivity carcass, extending its use beyond the Steiner mincuts it represents.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Noncrossing is All You Need: Beyond Identical Delay Functions in Online Matching with Delays on General Metrics
Quadratic-Time Barriers from Self-Referential SAT
Sublinear Metric Distortion for Matching
Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space
Near linear mixing of random-cluster Glauber dynamics on random regular graphs
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.