Vertex Sparsification for Edge Connectivity in Polynomial Time
summary
Constructs c-edge-connectivity mimicking networks with about k c^3 edges (or kc^3 · polylog n) in randomized polynomial time, improving prior kc^4-size constructions whose runtimes blow up for large c. The algorithm first reduces terminals to degree-1 terminals (blowing k by c), then recursively sparsest-cut partitions to bound the smaller-side terminal count d = O(c·polylog n), and finally uses matroid representative sets (gammoids over vertex cuts) to prove at most O(k c (c + d)) essential edges, so contracting nonessential edges yields the small mimicker; approach extends to hypergraphs.
AI-written summary · about