Given an undirected graph G = (V, E) with edge capacities ce ≥ 1 for e ∈ E and a subset T of k vertices called terminals, we say that a graph H is a quality-q cut sparsifier for G iff T ⊆ V (H), and for any partition (A, B) of T , the values of the minimum cuts separating A and B in graphs G and H are within a factor q from each other. We say that H is a quality-q flow sparsifier for G iff T ⊆ V (H), and for any set D of demands over the terminals, the values of the minimum edge congestion incurred by fractionally routing the demands in D in graphs G and H are within a factor q from each other. So far vertex sparsifiers have been studied in a restricted setting where the sparsifier H is not allowed to contain any non-terminal vertices, that is V (H) = T . For this setting, efficient algorithms are known for constructing quality-O(log k/ log log k) cut and flow vertex sparsifiers, as well as a lower bound ofΩ( √ log k) on the quality of any flow or cut sparsifier. We study flow and cut sparsifiers in the more general setting where Steiner vertices are allowed, that is, we no longer require that V (H) = T . We show algorithms to construct constant-quality cut sparsifiers of size O(C 3 ) in time poly(n) · 2 C , and constant-quality flow sparsifiers of size C O(log log C) in time n O(log C) · 2 C , where C is the total capacity of the edges incident on the terminals.
Chuzhoy REF gives a constant quality cut and flow sparsifiers with size depending on the total capacity of the edges on the terminals.
On vertex sparsifiers with Steiner nodes
STOC '12
Mathematics Computer Science