On Vertex Sparsifiers with Steiner Nodes

Julia Chuzhoy

Source-linked AI summary

On Vertex Sparsifiers with Steiner Nodes

Julia Chuzhoy

arXiv:1204.2844v1Apr 12, 2012cs.DS

TL;DR

The paper asks whether allowing Steiner vertices can improve vertex sparsifiers beyond the terminal-only setting. It constructs cut and flow sparsifiers using well-linked decompositions and routing techniques, obtaining constant-quality graphs with sizes and construction times parameterized by terminal-incident capacity.

Problem
Earlier vertex sparsifiers excluded Steiner vertices, motivating the question of whether allowing them can improve quality while keeping the sparsifier small.
Source: §1 · p. 2
Method
The paper constructs sparsifiers by contracting clusters from well-linked decompositions for cuts and using good routers for flows.
Source: §1 · pp. 3–4
Results
Cut sparsifiers have constant quality and size O(C^3), while flow sparsifiers have constant quality and size C^{O(log log C)}, with construction times poly(n) · 2^C and n^{O(log C)} · 2^C, respectively.
Source: §1 · p. 3
Takeaways & Limitations
The constructions show that constant-quality cut and flow sparsifiers can be obtained when Steiner vertices are allowed, with size governed by terminal-incident capacity C.
Source: §1 · p. 3
The introduction first treats the unit-capacity special case before extending the results to arbitrary capacities.
Source: §1 · p. 2, §2 · p. 5

Abstract

from arXiv · show

Given an undirected graph $G=(V,E)$ with edge capacities $c_e\geq 1$ for $e\in 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\subseteq 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\subseteq 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 $\tilde{\Omega}(\sqrt{\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)\cdot 2^C$, and constant-quality flow sparsifiers of size $C^{O(\log\log C)}$ in time $n^{O(\log C)}\cdot 2^C$, where $C$ is the total capacity of the edges incident on the terminals.

1 Introduction

The introduction asks whether allowing Steiner vertices can yield smaller, better-quality cut and flow sparsifiers, and presents constant-quality constructions parameterized by terminal-incident capacity. It outlines well-linked decompositions for cuts and good routers for flows.

1 Introduction

Earlier sparsifier definitions required H to contain only terminals, motivating the study of whether Steiner vertices can improve quality while keeping H small.The introduction connects compact sparsifiers to approximation algorithms whose solution values depend on terminal cuts or routing congestion.Source: §1 · p. 2

Our Results and Techniques

For arbitrary capacities, cut sparsifiers achieve quality 3 + ε with O(C^3) vertices, while flow sparsifiers achieve quality 68 + ε with C^{O(log log C)} vertices.C is the total capacity of edges incident on terminals.Source: §1 · pp. 3–4
The cut construction runs in poly(n) · 2^C time, and the flow construction runs in n^{O(log C)} · 2^C time.Source: §1 · pp. 3–4
For cuts, a new well-linked decomposition produces 1/3-well-linked clusters, with O(z^3) clusters for z boundary edges, which are contracted to form a constant-quality sparsifier.The paper contrasts this approach with prior techniques based on 0-extensions.Source: §1 · pp. 3–4
For flows, a good router is 1/3-well-linked and can route 1/z flow between every pair of its z boundary edges with constant congestion.Contracting disjoint good routers affects routing congestion by at most a constant factor.Source: §1 · p. 4
The flow algorithm iteratively finds a witness certifying that the nonterminals are a good router or contracts to a smaller legal graph, then outputs a contracted graph once it is small enough.The described witness uses disjoint well-linked sets and edge-disjoint paths linking terminals to their boundaries.Source: §1 · pp. 4–5

2 Preliminaries and Notation

The preliminaries define well-linkedness and demand-routing notation used to decompose graph regions and reason about routing. They also distinguish weak and strong well-linked decompositions, with the strong version trading higher running time and more boundary edges for stronger guarantees.

The section presents definitions and results first for unit-capacity graphs, then extends them to general capacities.Source: §2 · p. 5
A demand set is γ-restricted when each terminal's total demand is at most γ, and routing congestion is the maximum flow load on any edge.Source: §2 · p. 5
For flows between edge sets, each source edge sends one unit, congestion is bounded by η, and each destination edge receives at most η units.Source: §2 · pp. 5–6
A set S is α-well-linked when every split has at least α times the smaller boundary size in crossing edges; for α < 1, this is equivalent to sparsest-cut value at least α.Source: §2 · pp. 6–7
Strong well-linked decomposition produces 1/3-well-linked parts with bounded counts across boundary-size scales, but takes 2^z · poly(n) time and increases adjacent-edge counts.Source: §2 · p. 7

3 Cut Sparsifiers

The cut-sparsifier construction contracts parts of a strong well-linked decomposition, preserving terminal cuts within a constant factor. It extends from unit capacities to arbitrary capacities with a sparsifier of size O(C^3).

With unit edge capacities, the theorem gives a quality-3 cut sparsifier with O(k^3) vertices and construction time poly(n) · 2^k, where k is the sum of terminal degrees.Source: §3 · p. 8
The unit-capacity construction partitions nonterminals into strong well-linked sets and contracts each set into a super-node, producing the sparsifier.Source: §3 · p. 8
To bound cut distortion, the proof moves each cluster wholly to one side and charges added cut edges to internal edges, yielding a cut of at most three times the original size.Source: §3 · p. 8
For arbitrary capacities, the construction gives a quality-(3 + ε′) cut sparsifier of size O(C^3), where C is the total capacity of edges incident on terminals.It caps capacities at C, replaces edges by parallel unit-capacity edges, then rescales the sparsifier edges.Source: §3 · p. 9

4 Flow Sparsifiers

Section 4 constructs flow sparsifiers by repeatedly applying witness-or-contraction steps to contract good routers or nonterminal sets, reducing graph size while preserving restricted-flow quality. For well-linked nonterminals, the construction achieves size k^O(log log k), quality 2η*, and runs in n^O(log k)·2^k time.

4 Flow Sparsifiers

Contracting disjoint good routers preserves restricted-flow quality within a factor 2η*, because 1-restricted demands entering and leaving each cluster can be routed inside it with congestion at most 2η*.A legal contracted graph is obtained by contracting terminal-free good routers.Source: §4 · p. 10
For unit-capacity graphs with degree-1 terminals and 1/3-well-linked nonterminals, Theorem 6 gives a legal contracted sparsifier of quality 2η* and size k^O(log log k), in 2^k · n^O(log k) time.The theorem’s construction is the main technical contribution of the section.Source: §4 · pp. 10–11
Decomposing nonterminals into O(k^3) well-linked clusters and sparsifying each cluster yields a global legal contraction with quality 2η*, size k^O(log log k), and 2^k · n^O(log k) running time.The cluster boundaries have at most k edges, allowing Theorem 6 to be applied to each cluster.Source: §4 · pp. 10–11

4.1 Proof of Theorem 6

Theorem 8’s algorithm either finds a contractible subset or a type-1 or type-2 witness whenever a legal contracted graph has more than F(k) nonterminals.Repeated contractions reduce the graph until it has at most F(k) nonterminals, where F(k)=k^O(log log k).Source: §4.1 · pp. 11, 15
Type-1 witnesses enable all terminal pairs to exchange 1/k flow with congestion at most 10; type-2 witnesses imply the same exchange with congestion at most 34.Either witness implies that the original nonterminal set is a good router.Source: §4.1 · pp. 13–15
For a type-2 witness, the iteration seeks r edge groups with path collections from terminals, then tests well-linkedness; failure yields a balanced partition with fewer crossing edges.The first two steps find edge-disjoint paths to the groups, while the third uses an AARV sparsest-cut procedure to verify well-linkedness.Source: §4.1 · pp. 15, 17, 18
For a type-1 witness, recursive balanced partitions and weak well-linked decompositions produce large well-linked subsets; a terminal flow either yields routes to their boundary edges or a contractible set.When the flow reaches ⌈k/2⌉, it gives edge-disjoint terminal-to-boundary paths; if it does not, the construction returns a contractible set.Source: §4.1 · pp. 18–19
Theorem 8 either finds a type-1 or type-2 witness, or returns a contractible set for contraction.A type-1 witness comprises well-linked vertex subsets and terminal-to-boundary paths; a type-2 witness is established by routing paths to edge groups and verifying well-linkedness.Source: §4.1 · p. 19
The final contracted graph has at most F(k) nonterminals and is a quality-(2η*) sparsifier.The algorithm applies Theorem 8 repeatedly, contracting a set whenever no type-1 or type-2 witness exists; it terminates after at most |V(G)| iterations.Source: §4.1 · p. 19
The algorithm runs in n^O(log k)·2^k time.The proof bounds the recursive running time by induction on k, with each recursive call using at most ⌈k/2⌉ boundary edges.Source: §4.1 · p. 20

B.1 Proof of Theorem 3

The proof repeatedly splits clusters along sparse cuts until every remaining cluster is well-linked. A charging argument bounds the total boundary size of the resulting partition.

B.1 Proof of Theorem 3

Each sparse cut splits a cluster into children whose boundary sizes are at most 0.51 times the parent’s, while charging the crossing edges to the smaller terminal boundary.The split uses a sparsity threshold of 1/(27 log z).Source: §B.1 · p. 22
When no sparse cut remains, every cluster is αW(z)-well-linked, since a cluster that was not well-linked would yield a cut below the algorithm’s threshold.The threshold is 1/(27 log z), with αW(z) = 1/(27αARV(z) log z).Source: §B.1 · p. 22
The charging analysis bounds each edge’s total direct and indirect charge by 1/24, supporting a total partition-boundary bound of at most 1.2 times the original boundary.An edge is directly charged at most 4 log z/(27 log z) = 1/25; indirect charges form a geometric series.Source: §B.1 · p. 22

B.2 Proof of Theorem 4

The algorithm recursively splits clusters with sparse cuts and stops when all remaining clusters are 1/3-well-linked. Level-based charging bounds the number of terminals and clusters, yielding an O(z^3) terminal total.

B.2 Proof of Theorem 4

The algorithm splits any cluster with a cut of sparsity below 1/3 and stops when every cluster is 1/3-well-linked, in time 2^z poly(n).It tests terminal bipartitions to find a minimum separating cut.Source: §B.2 · p. 23
For each level i > 1, there are at most 2^(i−2)z special terminals and 2^(i−1)z regular terminals; level 1 has z special and at most z/2 regular terminals.Levels classify clusters by boundary size, and terminals are labeled regular or special according to when their edges arise.Source: §B.2 · pp. 23–24
The final partition has O(z^3) total boundary terminals, since the terminal count is bounded by 3z · 2^(2 log z).The algorithm’s partition has one associated terminal per boundary edge.Source: §B.2 · pp. 23–24
The number of level-i clusters is at most 2^(3i/2), and the combined size of cluster collections Si is at most 2^(3i+3).These bounds follow from the per-level terminal limits and the minimum boundary size of a level-i cluster.Source: §B.2 · p. 25

C Proof of Corollary 1

The construction converts terminal incident capacity into degree-one terminals, applies a flow-sparsifier construction, and then reunifies each terminal’s split vertices. Capacity normalization extends the guarantee to general edge capacities.

C Proof of Corollary 1

For integral capacities, replacing edges by unit-capacity parallels and subdividing terminal-incident edges creates C degree-one terminals before the intermediate sparsifier is built.The construction then unifies the split vertices associated with each original terminal.Source: C Proof of Corollary 1 · p. 25
Routing demands through the transformed terminals transfers a routing between G and H, while the reverse direction incurs a factor 2η*.The two directions use the corresponding flow-sparsifier guarantee for the intermediate graph.Source: C Proof of Corollary 1 · p. 25
For arbitrary capacities, the proof caps edges above C and changes capacities while bounding the resulting congestion distortion to obtain the additive-ε quality guarantee.C is the total capacity of edges incident on the terminals.Source: C Proof of Corollary 1 · pp. 25–26
The resulting flow sparsifier has quality 2η* + ε and size C^O(log log C).The construction scales capacities of an intermediate sparsifier to obtain the guarantee for the original graph.Source: C Proof of Corollary 1 · p. 26

D.1 Proof of Claim 3

The proof shows that contracting the clusters preserves well-linkedness up to a factor of three. It does so by moving each cluster wholly to one side of a cut and charging the new cut edges to edges internal to that cluster.

D.1 Proof of Claim 3

Moving each cluster to one side adds at most three times as many cut edges as the original violating cut, while leaving the terminal partition unchanged.The internal edges used for charging are not charged again, yielding a contradiction to α-well-linkedness in the contracted graph.Source: §D.1 · pp. 26–27

D.2 Proof of Claim 4

The proof shows that a hypothetical low-capacity cut in N1 would yield a cut in N2 contradicting the flow guaranteed by the path set. It rounds cuts across clusters while controlling the increase in capacity.

D.2 Proof of Claim 4

N1 uses G with capacity 3η on internal network edges, while N2 uses G′ with capacity η; source and sink edges have capacity 1.N1 connects the source to T ′ and subdivides each edge in E′ to connect it to the sink; N2 is constructed similarly on G′.Source: §D.2 · p. 27
A cut below |T ′| in N1 yields an N2 cut below |T ′|, contradicting the flow guaranteed by the path set.The rounded cut preserves the source- and sink-edge count, while the remaining crossing-edge count grows by at most a factor of 3.Source: §D.2 · pp. 27–28
Each super-node’s cluster is moved wholly to the side that minimizes the corresponding count of outgoing edges across the cut.The choice compares |EX| + |EXY| with |EY| + |EYX|.Source: §D.2 · p. 27
Because each cluster is 1/3-well-linked, its internal crossing edges can cover the relevant EX edges with at most 3 charges per edge.For the case where the cluster is moved to Y, |EC| ≥ |EX|/3.Source: §D.2 · p. 27
The rounding keeps source- and sink-incident cut edges unchanged and increases the other crossing-edge count by at most a factor of 3.With capacities 1 on source- and sink-incident edges and 3η on the other edges, the resulting N2 cut has capacity below |T ′|.Source: §D.2 · pp. 27–28