Deterministic Minimum Steiner Cut in Maximum Flow Time

Abstract

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/\hat{I}{\mu }^4)}$ maximum flow calls and additional $O(m^{1+\hat{I}\mu })$ time, for $\hat{I}\mu >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.

18 pages, 1 figure, to appear at ESA 2024