Deterministic Almost-Linear-Time Gomory-Hu Trees

Given an undirected, weighted graph $G=(V, E, w)$, a Gomory-Hu tree or cut tree (Gomory and Hu, 1961) is a tree T over the vertex set V such that for every pair of vertices $s, t \in V$, the ($s, t$) min-cut in T is also an ($s, t$) min-cut in G and has the same value. In this article, we give the first deterministic almost-linear-time algorithm for constructing a Gomory-Hu tree. Our algorithm runs in $m^{1+o(1)}$-time, where m denotes the number of edges in the input graph G; this is clearly optimal up to the $m^{o(1)}$ term in the running time. Prior to our work, the best deterministic algorithm for this problem dated back to the original algorithm of Gomory and Hu that runs in $n m^{1+o(1)}$ time using current maxflow algorithms. In fact, our algorithm is also the first almost-linear-time deterministic algorithm for even simpler problems, such as finding the k-edge-connected components of a graph. Our new result hinges on two separate and novel components that each introduce a distinct set of de-randomization tools of independent interest: - a deterministic reduction from the all-pairs min-cuts problem to the single-source min-cuts problem incurring only sub-polynomial overhead, and - a deterministic almost-linear time algorithm for the singlesource min-cuts problem.

Authors

• Amir Abboud
• Rasmus Kyng
• Jason Li 0006
• Debmalya Panigrahi
• Maximilian Probst Gutenberg
• Thatchaphol Saranurak
• Weixuan Yuan
• Wuwei Yuan

Keywords

• Computer science
• Tree graphs
• Trees (botanical)
• Fasteners
• Indexes
• Gomory-Hu Tree
• Running Time
• Undirected
• Algorithm For Problem
• Pair Of Vertices
• Input Graph
• Components Of The Graph
• Deterministic Time
• Tree Cut
• Line Of Work
• Linear Time
• Vertices
• Recursive Algorithm
• Interior Point Method
• Simple Graph
• Dynamic Graph
• Edge Connectivity
• Graph Algorithms
• Index Terms-Gomory-Hu trees
• deterministic algorithms