Preconditioning and Locality in Algorithm Design
summary
Shows that Steiner min-cut reduces to an unbalanced case that can be solved with a polylogarithmic number of max‑flow calls: isolating every terminal takes O(log |R|) max‑flow executions and gives the unbalanced Steiner min‑cut. General instances reduce by random sampling (sampling rate ~1/|smaller side| gives constant probability of picking exactly one terminal; use geometric scales to find the right rate). Deterministic guarantees come from preconditioning via expander decomposition and exploiting locality so the small side is only polylogarithmic.
AI-written summary · about