Cut-Approximators, Approximating Undirected Max Flows, and Recursion
summary
Presents a concrete recursive recipe that yields a nearly‑linear time (1+ε)-approximation for undirected max flow by combining alpha cut approximator trees (polylog α), the almost-route solver with O~(α^2 ε^-2) iterations, and size reduction via ultra-sparsifiers plus Madry-style off-tree compression. Uses κ-parameter sparsifiers to shrink instances to O~(m/κ) edges, converts back with constant loss, picks κ≈polylog n to get the recurrence T(M)=T(M/2)+m polylog n, and achieves the claimed fast runtime while relying on existing near-linear solvers.
AI-written summary · about