On vertex sparsifiers with Steiner nodes
Julia Chuzhoy · 2012
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.