3 papers
cs.DS2026
Maximum Flow Without the Outer IPM
Jason Li, Alex Wice
We show that the balancing weights technique of Li (2026) actually produces an approximate *pseudo-circulation* of a directed, capacitated graph in time. Together with…
cs.DS2025
Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time
Antoine El-Hayek, Monika Henzinger, Jason Li
We present an exact fully-dynamic minimum cut algorithm that runs in deterministic update time when the minimum cut size is at most for any ,…
cs.DS2025
Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation
Antoine El-Hayek, Monika Henzinger, Jason Li
Dynamically maintaining the minimum cut in a graph under edge insertions and deletions is a fundamental problem in dynamic graph algorithms for which no conditional lower bound…