Deterministic Minimum Steiner Cut in Maximum Flow Time

We devise a deterministic algorithm for minimum Steiner cut, which uses \((\log n)^{O(1)}\) maximum flow calls and additional near-linear time. This algorithm improves on Li and Panigrahi’s (FOCS 2020) algorithm, which uses \((\log n)^{O(1/\epsilon^4)}\) maximum flow calls and additional \(O(m^{1+\epsilon})\) time, for \(\epsilon > 0\). Our algorithm thus shows that deterministic minimum Steiner cut can be solved in maximum flow time up to polylogarithmic factors, given any black-box deterministic maximum flow algorithm. Our main technical contribution is a novel deterministic graph decomposition method for terminal vertices that generalizes all existing s-strong partitioning methods, which we believe may have future applications.

Matthew Ding and Jason Li. European Symposium on Algorithms (ESA 2024).
Download Paper | Download Slides