Ta-Wei Tu

FOCS Conference 2025 Conference Paper

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs

• Aaron Bernstein
• Joakim Blikstad
• Jason Li 0006
• Thatchaphol Saranurak
• Ta-Wei Tu

We give a combinatorial algorithm for computing exact maximum flows in directed graphs with n vertices and edge capacities from {1, …, U} in $\tilde O\left({{n^2}\log U}\right)$ time, which is near-optimal on dense graphs. This shaves an n o(1) factor from the recent result of [Bernstein–Blikstad–Saranurak–Tu FOCS’24] and, more importantly, greatly simplifies their algorithm. We believe that ours is by a significant margin the simplest of all algorithms that go beyond $\tilde O(m\sqrt n )$ time in general graphs. To highlight this relative simplicity, we provide a full implementation of the algorithm in C++. The only randomized component of our work is the cut-matching game. Via existing tools, we show how to derandomize it for vertex-capacitated max flow and obtain a deterministic $\tilde O\left({{n^2}}\right)$ time algorithm. This marks the first deterministic near-linear time algorithm for this problem (or even for the special case of bipartite matching) in any density regime.

SODA Conference 2025 Conference Paper

Entropy Regularization and Faster Decremental Matching in General Graphs

• Jiale Chen 0003
• Aaron Sidford
• Ta-Wei Tu

SODA Conference 2025 Conference Paper

Matching Composition and Efficient Weight Reduction in Dynamic Matching

• Aaron Bernstein
• Jiale Chen 0003
• Aditi Dudeja
• Zachary Langley
• Aaron Sidford
• Ta-Wei Tu

FOCS Conference 2024 Conference Paper

Maximum Flow by Augmenting Paths in n 2+o(1) Time

• Aaron Bernstein
• Joakim Blikstad
• Thatchaphol Saranurak
• Ta-Wei Tu

We present a combinatorial algorithm for computing exact maximum flows in directed graphs with $n$ vertices and edge capacities from $\{1, \ldots, U\}$ in $n^{2+o(1)}\log U$ time, which is almost optimal in dense graphs. Our algorithm is a novel implementation of the classical augmenting-path framework; we list augmenting paths more efficiently using a new variant of the push-relabel algorithm that uses additional edge weights to guide the algorithm, and we derive the edge weights by constructing a directed expander hierarchy. Even in unit-capacity graphs, this breaks the long-standing $O(m \cdot\min\{\sqrt{m}, n^{2/3}\})$ time bound of the previous combinatorial algorithms by Karzanov (1973) and Even and Tarjan (1975) when the graph has $m=\omega(n^{4/3})$ edges. Notably, our approach does not rely on continuous optimization nor heavy dynamic graph data structures, both of which are crucial in the recent developments that led to the almost-linear time algorithm by Chen et al. (FOCS 2022). Our running time also matches the $n^{2+o(1)}$ time bound of the independent combinatorial algorithm by Chuzhoy and Khanna (STOC 2024) for computing the maximum bipartite matching, a special case of maximum flow.

STOC Conference 2023 Conference Paper

Fast Algorithms via Dynamic-Oracle Matroids

• Joakim Blikstad
• Sagnik Mukhopadhyay
• Danupon Nanongkai
• Ta-Wei Tu

We initiate the study of matroid problems in a new oracle model called dynamic oracle . Our algorithms in this model lead to new bounds for some classic problems, and a “unified” algorithm whose performance matches previous results developed in various papers for various problems. We also show a lower bound that answers some open problems from a few decades ago. Concretely, our results are as follows. Improved algorithms for matroid union and disjoint spanning trees. We show an algorithm with Õ k ( n + r √ r ) dynamic-rank-query and time complexities for the matroid union problem over k matroids, where n is the input size, r is the output size, and Õ k hides poly ( k , log( n )). This implies the following consequences. (i) An improvement over the Õ k ( n √ r ) bound implied by [Chakrabarty-Lee-Sidford-Singla-Wong FOCS’19] for matroid union in the traditional rank-query model. (ii) An Õ k (| E |+| V |√| V |)-time algorithm for the k -disjoint spanning tree problem. This is nearly linear for moderately dense input graphs and improves the Õ k (| V |√| E |) bounds of Gabow-Westermann [STOC’88] and Gabow [STOC’91]. Consequently, this gives improved bounds for, e.g., Shannon Switching Game and Graph Irreducibility. Matroid intersection. We show a matroid intersection algorithm with Õ( n √ r ) dynamic-rank-query and time complexities. This implies new bounds for some problems (e.g. maximum forest with deadlines) and bounds that match the classic ones obtained in various papers for various problems, e.g. colorful spanning tree [Gabow-Stallmann ICALP’85], graphic matroid intersection [Gabow-Xu FOCS’89], simple job scheduling matroid intersection [Xu-Gabow ISAAC’94], and Hopcroft-Karp combinatorial bipartite matching. More importantly, this is done via a “unified” algorithm in the sense that an improvement over our dynamic-rank-query algorithm would imply improved bounds for all the above problems simultaneously. Lower bounds. We show simple super-linear (Ω( n log n )) query lower bounds for matroid intersection and union problems in our dynamic-rank-oracle and the traditional independence-query models; the latter improves the previous log 2 (3) n − o ( n ) bound by Harvey [SODA’08] and answers an open problem raised by, e.g., Welsh [1976] and CLSSW [FOCS’19].