VERTEX SPARSIFICATION AND OBLIVIOUS REDUCTIONS.

Given an undirected, capacitated graph G = (V, E) and a set K ⊂ V of terminals of size k, we construct an undirected, capacitated graph G' = (K, E') for which the cut function approximates the value of every minimum cut separating any subset U of terminals from the remaining terminals K - U. We refer to this graph G' as a cut-sparsifier, and we prove that there are cut-sparsifiers that can approximate all these minimum cuts in G to within an approximation factor that depends only polylogarithmically on k, the number of terminals. We prove such cut-sparsifiers exist through a zero-sum game, and we construct such sparsifiers through oblivious routing guarantees. These results allow us to derive a more general theory of Steiner cut and flow problems, and allow us to obtain approximation algorithms with guarantees independent of the size of the graph for a number of graph partitioning, graph layout, and multicommodity flow problems for which such guarantees were previously unknown. [ABSTRACT FROM AUTHOR]