Tootfinder

Deterministic Almost-Linear-Time Gomory-Hu Trees
Amir Abboud, Rasmus Kyng, Jason Li, Debmalya Panigrahi, Maximilian Probst Gutenberg, Thatchaphol Saranurak, Weixuan Yuan, Wuwei Yuan
https://arxiv.org/abs/2507.20354

Deterministic Almost-Linear-Time Gomory-Hu Trees
Given an $m$-edge, undirected, weighted graph $G=(V,E,w)$, a Gomory-Hu tree $T$ (Gomory and Hu, 1961) is a tree over the vertex set $V$ such that all-pairs mincuts in $G$ are preserved exactly in $T$. In this article, we give the first almost-optimal $m^{1+o(1)}$-time deterministic algorithm for constructing a Gomory-Hu tree. Prior to our work, the best deterministic algorithm for this problem dated back to the original algorithm of Gomory and Hu that runs in $nm^{1+o(1)}$ time (using current…

A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
Amir Abboud, Shyan Akmal, Nick Fischer
https://arxiv.org/abs/2507.18845 https://arxi…

A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
We present the first truly subcubic, combinatorial algorithm for detecting an induced $4$-cycle in a graph. The running time is $O(n^{2.84})$ on $n$-node graphs, thus separating the task of detecting induced $4$-cycles from detecting triangles, which requires $n^{3-o(1)}$ time combinatorially under the popular BMM hypothesis. Significant work has gone into characterizing the exact time complexity of induced $H$-detection, relative to the complexity of detecting cliques of various sizes. Prior…