Tata Institute of Fundamental Research

All-Pairs kth Mincuts: Combinatorial and Structural Results

STCS Student Seminar
Speaker: Anupam Roy (IIT Kanpur)
Organiser: Soumyajit Pyne
Date: Friday, 20 Nov 2026, 16:00 to 17:00
Venue: via Zoom in A201

(Scan to add to calendar)
Abstract: 

Minimum cuts are fundamental objects in graph theory. They often admit interesting combinatorial results like the Maxflow-Mincut Theorem and compact representations like the Gomory-Hu tree. The classical Gomory-Hu tree shows that although there are overall $\Omega(n^2)$ pairs of vertices, a single spanning tree compactly preserves all of their mincut values. But does any such structure survive when we move beyond the optimum? 

We study this question for $k^{th}$ minimum value cuts, in short, \emph{$k^{th}$-mincuts}, for all pairs of vertices. We show that the Gomory–Hu phenomenon interestingly extends beyond minimum cuts: the $k^{th}$-mincut values between all pairs of vertices can be preserved by storing only $k$ spanning trees. This yields a tight bound of $O(\min\{kn,n^2\})$ on the number of distinct values. 
Going beyond values, we show that the cuts themselves also admit a compact representation: a collection of only $O(k\log n)$ tree-like structures suffices to store a $k^{th}$ mincut for each pair of vertices. These structural results further lead to compact data structures that given any pair of vertices $(u,v)$, can report a $k^{th}$ $(u,v)$-mincut and its value efficiently.

Overall, in this talk, we show that the strong redundancies that exist among all-pairs mincuts does not disappear beyond the optimum -- it continues to exists for all-pairs $k^{th}$ mincuts, even for $k>1$.