Cut-Preserving Vertex Sparsifiers for Planar and Quasi-Bipartite Graphs

Our construction of planar cut sparsifiers follows a similar framework as the planar distance emulator construction in [5], based on the intuition that, if we take the dual graph, then min-cuts become min-length partitioning cycles and therefore can be approximated by distance-based approaches. The algorithm consists of three steps:

1. 1.

   reduce general planar graphs to $O(1)$-face instances (where terminals lie on $O(1)$ faces in the planar embedding of the graph);

2. 2.

   reduce $O(1)$-face instances to $1$-face instances (where all terminals lie on the boundary of a single face; such graphs are also known as Okamura-Seymour instances); and

3. 3.

   construct quality-$(1+\epsilon )$ planar cut sparsifiers for $1$-face instances.

Step $1$ and Step $3$ are implemented in a similar way as [5]. Step $2$ requires several new ideas. The goal is to preserve the min-cuts for all terminal partitions. As terminals may lie on $O(1)$ faces, for different terminal partitions, the dual partitioning cycle corresponding to the min-cuts may go around these $O(1)$ faces in different ways, and therefore it is not enough to just preserve pairwise shortest paths in the dual graph. Indeed, as observed by [29], we need to preserve, for each pair of terminals, and for each pattern (how a path going around the $O(1)$ faces, e.g., on the left side of face $1$, on the right side of face $2$, etc), the shortest path following the pattern and connecting the terminal pair. We call such a sparsifier a pattern distance emulator, which a generalization of the standard distance emulators. As there are $O(1)$ faces, there are $2^{O(1)}$ different patterns (left/right for each face). We manage to construct a near-linear size pattern emulator, incurring an unharmful factor $2^{O(1)}$ loss in its size.

We believe that the notion of pattern emulators is of independent interest, and should play a role in solving other algorithmic problems on planar graphs.

For exact (quality-$1$) contraction-based cut sparsifiers, a central notion in previous constructions and lower bound proofs is the profiles of vertices. Specifically, the profile of a vertex $v$ specifies, for each terminal partition $(S,T\setminus S)$, on which side of the cut ${\mathrm{𝗆𝗂𝗇𝖼𝗎𝗍}}_G(S,T\setminus S)$ lies the vertex $v$. Vertices of the same profile can be safely contracted together, and the number of different profiles is therefore an upper bound on the size of exact cut sparsifiers. For general graphs, a doubly-exponential upper bound of $2^{2^k}$ [18] on the number of distinct profiles was established, and this was later improved to $2^{\left(\genfrac{}{}{0pt}{}{k}{k/2}\right)}$ [24]. For quasi-bipartite graphs, we will utilize its structure to proved a better (single-exponential) upper bound.

By the definition of quasi-bipartite graphs, there are no edge between non-terminal vertices, so non-terminal vertices form separate stars with terminals, and therefore contribute to terminal min-cuts independently. For example, in a star centered at $v$ with $6$ edges $e_1,\mathrm{\dots },e_6$ connecting to terminal $t_1,\mathrm{\dots },t_6$, respectively. The profile of vertex $v$ only depends on the weights of the edges $e_1,\mathrm{\dots },e_6$: for the terminal partition $(S=\{t_1,t_2,t_3\},T\setminus S=\{t_4,t_5,t_6\})$,

This gives us some power to reveal properties of profiles in quasi-bipartite graphs. For example, if we consider subsets $S\subseteq T$ being $\{1,2\},\{3,4\},\{1,3\},\{2,4\}$, then $v$ cannot lie on the $S$ side for all these terminal min-cuts. Since otherwise, letting $w={\sum }_{1\le i\le 6}w(e_i)$, we get $w(e_1)+w(e_2)>w/2$, $w(e_3)+w(e_4)>w/2$, $w(e_1)+w(e_3)\le w/2$, and $w(e_2)+w(e_4)\le w/2$, a contradiction. This means that there are some “configurations” in the family of terminal subsets that are simply not realizable by any vertex profiles in quasi-bipartite graphs. We implement this idea through the notion of VC-dimension, realizing “configurations” by “set systems” and “not realizable” by “non-shatterable”, and obtain a bound of $k^{O(k^2)}=2^{O(k^2\log k)}$ on the number of profiles in quasi-bipartite graphs.

For quality-$(1+\epsilon )$ cut sparsifiers, since we allow a small multiplicative error in accuracy, we are not restricted to contracting vertices with the same profile, but are allowed to moderately manipulate vertex profiles so as to reduce their number. We implement this idea by “projections onto $O(1/{\epsilon }^2)$-size stars”. On the one hand, consider for example a full star centered at $v$ (that is, a star containing edges $(v,t)$ for all $t\in T$) with uniform edge weights, and a subset $S\subseteq T$ with $|S|=|T|/2-1$, so $v$ lies on the $T\setminus S$ side of ${\mathrm{𝗆𝗂𝗇𝖼𝗎𝗍}}_G(S,T\setminus S)$. If we uniformly at random sample $c=O(1/{\epsilon }^2)$ edges from it and obtain a “mimicking substar” $H_v$, then by central limit theorem, with high probability $H_v$ contains at most $c/2+O(1/\epsilon )$ edges to $S$ and at least $c/2-O(1/\epsilon )$ edges to $T\setminus S$. Therefore, even if $H_v$ fails in mimicking the behavior of the full star on the cut $(S,T\setminus S)$, in that it mistakenly selects more edges to $S$ than to $T\setminus S$ and therefore place $v$ on the $S$ side of ${\mathrm{𝗆𝗂𝗇𝖼𝗎𝗍}}_G(S,T\setminus S)$ rather than the $T\setminus S$ side, it only causes an error of $\frac{c/2+O(1/\epsilon )}{c/2-O(1/\epsilon )}=1+O(\epsilon )$ in the min-cut size, which is allowed.

On the other hand, we have shown in the exact case that the number of profiles for stars on a fixed $O(1/{\epsilon }^2)$-size terminal set is $O{(1/{\epsilon }^2)}^{O(1/{\epsilon }^4)}$ (replacing $k$ with $O(1/{\epsilon }^2)$ in the $k^{O(k^2)}$ bound). Since the number of $O(1/{\epsilon }^2)$-size terminal subsets is $k^{O(1/{\epsilon }^2)}$, we can bound the total number of profiles produced by $O(1/{\epsilon }^2)$-size starts by $k^{O(1/{\epsilon }^2)}\cdot O{(1/{\epsilon }^2)}^{O(1/{\epsilon }^4)}$, obtaining a size bound of $k^{O(1/{\epsilon }^2)}f(\epsilon )$ for quality-$(1+\epsilon )$ contraction-based cut sparsifiers for quasi-bipartite graphs.

As shown in [10, 9], contraction-based sparsifiers are closely related to the Steiner node version of the classic $0$-Extension problem [23]. Specifically, [10] showed that the best quality achievable by contraction-based flow sparsifiers is bounded by the integrality gap of the semi-metric LP relaxation. For cut sparsifiers, we observe that the best achievable quality is controlled by an even more restricted case of the $0$-Extension with Steiner Nodes problem, where the underlying graph is a boolean hypercube. We focus on this special case, construct a hard hypercube-instance which is also a quasi-bipartite graph, and prove a size lower bound for its $(1+\epsilon )$-approximation, leading to a same size lower bound for quality-$(1+\epsilon )$ contraction-based cut sparsifiers for quasi-bipartite graphs.

Independent of work, Das, Kumar, and Vaz, showed in their work [12] that quasi-bipartite graphs admit exact non-contraction-based cut sparsifiers of size $2^{k^2}$ and exact contraction-based cut sparsifiers of size $2^{k^3}$. Our Theorem 2 gives a $2^{O(k^2\log k)}$ size bound for exact contraction-based cut sparsifiers, which is slightly stronger than their $2^{k^3}$ bound, and slightly weaker than their $2^{k^2}$ bound. They also have some results on flow sparsifiers. For example, quasi-bipartite graphs admit exact flow sparsifiers of size $3^{k^3}$, and treewidth-$w$ graphs admit quality-$O(\frac{\log w}{\log \log w})$ flow sparsifiers of size $O(kw)$.

After Karger’s result [21] on cut-preserving edge sparsifiers, there are other work using sampling-based approaches. Benzcur and Karger [3] sampled edges based on inverse edge-strengths, and obtained a sparsifier of $O(n\log n/{\epsilon }^2)$ edges. Fung and Harvey [14] sampled edges according to their inverse edge-connectivity, and also obtained the bound of $O(n{\log }^{2}n/{\epsilon }^2)$. Spielman and Srivastava [36] sampled edges based on their inverse effective-resistance to obtain a spectral sparsifier (a generalization of cut sparsifiers) with size $O(n\log n/{\epsilon }^2)$. This bound was later improved by Batson, Spielman, and Srivastava [2] to $O(n/{\epsilon }^2)$.

There are some work on (i) constructing better cut sparsifiers for special families of graphs, for example trees [16] and planar graphs with all terminals lying on the same face [15], and graphs with bounded treewidth [1]; (ii) preserving terminal min-cut values up to some threshold value [4, 31]; and (iii) dynamic cut/flow sparsifiers and their utilization in dynamic graph algorithms [13, 7, 17].

Flow sparsifiers are highly correlated with cut sparsifiers. Given a graph $G$ and a set $T$ of $k$ terminals, a graph $G^{\prime }$ is a flow sparsifier of $G$ with respect to $T$ with quality $q$, iff every $G$-feasible multicommodity flow on $T$ can be routed in $G^{\prime }$, and every $G^{\prime }$-feasible multicommodity flow on $T$ can be routed in $G$ if the capacities of edges in $G$ are increased by factor $q$. Flow sparsifiers are stronger than cut sparsifiers, in the sense that quality-$q$ flow sparsifiers are automatically quality-$q$ cut sparsifiers, but the other direction is not true in general.

When no Steiner nodes are allowed, Leighton and Moitra [30] showed the existence of quality-$O(\log k/\log \log k)$ flow sparsifiers. On the lower bound side, the first quality lower bound in [30] is $\mathrm{\Omega }(\log \log k)$, and this was later improved to $\mathrm{\Omega }(\sqrt{\log k/\log \log k})$ by Makarychev and Makarychev [32].

In the setting where Steiner nodes are allowed, Chuzhoy [11] showed $O(1)$-quality contraction-based flow sparsifiers with size $C^{O(\log \log C)}$ exist, where $C$ is the total capacity of all edges incident to terminals (assuming that all edges have capacity at least $1$). On the lower bound side, Krauthgamer and Mosenzon [27] showed that there exist $6$-terminal graphs whose quality-$1$ flow sparsifiers must have an arbitrarily large size (i.e., the size bound cannot depend only on $k$ and $\epsilon$). Chen and Tan [10] showed that there exists $6$-terminal graphs whose quality-$(1+{10}^{-18})$ contraction-based flow sparsifiers must have an arbitrarily large size.

Cuts in planar graphs are cycles in their dual graphs. We will exploit this property in a similar way as [29] and transform the cut-preserving tasks to distance-preserving tasks. For technical reasons, in order to handle graphs with terminals, our definition of dual graphs are slightly different from the standard planar dual graphs.

Let $(G,T)$ be the input instance and let $ℱ$ be the faces that contains all terminals. Assume each face is a simple cycle. For each $F\in ℱ$, add an auxiliary vertex $x_F$, and connect it to every terminal via a new edge, such that these edges are drawn in an internally disjoint way within face $F$, so that they separates face $F$ into subfaces, which we call special subfaces. Then we take the standard planar dual of the modified graph. Here each special face correspond to a node, which we call dual terminals. We then remove all edges in the dual graph connecting a pair of dual terminals. We denote the resulting graph by $G^{\ast }$, and denote by $T^{\ast }$ the set of dual terminals. See Figure 1 for an illustration. Note that when graph $G$ does not have the property that each face is a simple cycle, as long as we are guaranteed that no terminal is a separator, we can still define dual graphs similarly. It is also easy to verify that the dual of the dual graph $G^{\ast }$ is the original graph $G$ itself. Sometimes we say that we reverse $G^{\ast }$ to obtain $G$. Finally, as both $G$ and $G^{\ast }$ are planar graphs, and each non-terminal vertex in $G^{\ast }$ corresponds to a face in $G$, the number of vertices in $G$ and $G^{\ast }$ are within $O(1)$ factor from each other.

We denote by ${ℱ}^{\ast }$ the faces in $G^{\ast }$ that contain all dual terminals. It is easy to see that there exists a natural one-to-one correspondence between $ℱ$ and ${ℱ}^{\ast }$.

For a pair $t,t^{\prime }$ of dual terminals in graph $G^{\ast }$, there are more than one way for them to be connected by a path, depending on how the path goes around other faces in ${ℱ}^{\ast }$, called patterns, A rigorous way of defining patterns was given in [29], which we describe below.

Fix a point ${\nu }^{\ast }$ in the plane. Let $\gamma$ be a closed curve (not necessarily simple). A vertex $v\notin \gamma$ is said to be inside $\gamma$ iff any simple curve connecting ${\nu }^{\ast }$ to $v$ crosses $\gamma$ an odd number of times, otherwise it is said to be outside $\gamma$. For a pair $t,t^{\prime }$ of dual terminals in $G^{\ast }$, we denote by ${\mathrm{\Pi }}_{t,t^{\prime }}$ the shortest path connecting them in $G^{\ast }$. For every face $F\in {ℱ}^{\ast }$, we place a point $z_F$ inside its interior. Consider now a path $P$ in $G^{\ast }$ connecting $t,t^{\prime }$. Note that the union of $P$ and ${\mathrm{\Pi }}_{t,t^{\prime }}$ is a closed curve. Now the pattern of $P$ is defined to be a $|{ℱ}^{\ast }|$-dimensional vector $\mathrm{\Phi }(P)={({\varphi }_F)}_{F\in {ℱ}^{\ast }}$, where ${\varphi }_F=1$ iff $z_F$ is inside the closed curve formed by the union of $P$ and ${\mathrm{\Pi }}_{t,t^{\prime }}$ and ${\varphi }_F=-1$ iff $z_F$ is outside.

Let $P,P^{\prime }$ be simple paths with same endpoints, the above definition of pattern implies that paths $P,P^{\prime }$ have the same pattern iff all points ${\left\{z_F\right\}}_{F\in {ℱ}^{\ast }}$ lie outside the closed curve $P\cup P^{\prime }$. We will also consider paths $P,P^{\prime }$ with one common endpoint $t$. Let $R$ be a path such that the other-endpoints of $P$ and $P^{\prime }$ both lie on $R$. In this case we say that paths $P,P^{\prime }$ have the same pattern with respect to $R$, iff all points ${\left\{z_F\right\}}_{F\in {ℱ}^{\ast }}$ lie ourside the closed curve formed by the union of $P$, $P^{\prime }$, and the subpath of $R$ between the other-endpoint of $P$ and the other-endpoint of $P^{\prime }$.

For a pattern $\mathrm{\Phi }$, the $t$-$t^{\prime }$ $\mathrm{\Phi }$-shortest path is defined to be the shortest path among all $t$-$t^{\prime }$ paths with pattern $\mathrm{\Phi }$. Its length is defined to be the $\mathrm{\Phi }$-distance between $t,t^{\prime }$, which we denote by ${\text{dist}}^{\mathrm{\Phi }}(t_1,t_2)$. Let $(G,T),(H,T)$ be aligned instances. We say that $(H,T)$ is a quality-$q$ pattern emulator of $(G,T)$, iff for every pair $t_1,t_2$ of terminals and every pattern $\mathrm{\Phi }$, the $\mathrm{\Phi }$-distance between $t_1,t_2$ in $G$ is within factor $q$ from the $\mathrm{\Phi }$-distance between $t_1,t_2$ in $H$. We use the following result from [29].

We use the notion of $\epsilon$-covers defined in [25, 37]. Let $R$ be a shortest path and let $v$ be a vertex that does not lie in $R$. An $\epsilon$-cover of $v$ in $R$ is a set $C(v,R)$ of vertices, such that for any vertex $x\in R$, there exists some $y\in C(v,R)$, such that $\text{dist}(v,x)\le \text{dist}(v,y)+\text{dist}(y,x)\le (1+\epsilon )\cdot \text{dist}(v,x).$ It has been shown [25, 37] that for every $\epsilon >0$, shortest path $R$ and vertex $v\notin R$, there exists an $\epsilon$-cover of $v$ in $R$ of size $O(1/\epsilon )$. As we want to construct pattern emulators, we will need to modify the definition of $\epsilon$-covers into a “pattern version” accordingly, as follows.

Let $G$ be an $f$-face instance, $R$ be a shortest path in $G$ that does not intersect any face internally, and $v$ be a vertex that does not lie in $R$. Let $Q$ be a path connecting $v$ to some vertex in $R$, and let $\mathrm{\Phi }$ be its pattern. A $\mathrm{\Phi }$-respecting $\epsilon$-cover of $v$ in $R$ is a set $C(v,R,\mathrm{\Phi })$ of vertices, such that for any vertex $x\in R$, there exists some $y\in C(v,R,\mathrm{\Phi })$, such that the shortest $v$-$y$ path with the same pattern as $\mathrm{\Phi }$, concatenated with the $y$-$x$ subpath of $R$, is within factor $(1+\epsilon )$ in length with the shortest $v$-$x$ path with the same pattern as $\mathrm{\Phi }$. In other words (slightly abusing the notations),

We use the following lemma, whose proof is similar to the previous result of $\epsilon$-cover and is deferred to the full version of the paper.

We now define a set $Y$ of vertices on $\mathrm{\Pi }$ as follows. For each terminal $t$ and for each pattern $\mathrm{\Phi }$, let $Y_{t,\mathrm{\Phi }}$ be the pattern-respecting ${\epsilon }^{\prime }$-cover of $v$ in $R$ of size $O(1/{\epsilon }^{\prime })$ given by Lemma 18. We then let set $Y={\bigcup }_{t,\mathrm{\Phi }}{Y}_{t,\mathrm{\Phi }}$. From Observation 15 and Lemma 18, $|Y|\le O(2^f\cdot |T|/{\epsilon }^{\prime })$.

We then slice the graph $G$ open along the path $\mathrm{\Pi }$ connecting faces $\alpha ,{\alpha }^{\prime }$. Specifically, we duplicate path $\mathrm{\Pi }$ into two copies ${\mathrm{\Pi }}_1,{\mathrm{\Pi }}_2$ and place them closely at two sides (which we call $1$-side and $2$-side, respectively) of its original image, such that the thin strip between them connect faces $\alpha ,{\alpha }^{\prime }$ into a single face $\beta$. All vertices $x$ on $P$ into their copies $x_1,x_2$ ($x_1$ lies on ${\mathrm{\Pi }}_1$ and $x_2$ lies on ${\mathrm{\Pi }}_2$), including the terminals $t,t^{\prime }$ that now have copies $t_1,t_2$ and $t_1^{\prime },t_2^{\prime }$. All weights on edges remain the same. It is easy to verify that the obtained graph, which we denote by $G^{\prime }$, is a $(f-1)$-face instance. Let $T^{\prime }$ be the set that contains all copies of terminals and portals in $Y$. We then construct a quality-$(1+{\epsilon }^{\prime \prime })$ pattern emulator $H^{\prime }$ of $G^{\prime }$ with respect to $T^{\prime }$, and then glue, for each portal $y\in Y$, its copies $y_1,y_2$ back to their original vertex $y$. The resulting graph is denoted by $H$ and is returned as the pattern emulator for $G$. For a complete description of the cut and glue operations, please refer to Appendix B of [5]. See Figure 2 for an illustration.

It remains to complete the proof by induction. We first bound the size of graph $H$.

Since graph $H$ is obtained from graph $H^{\prime }$ by gluing the portals on paths ${\mathrm{\Pi }}_1,{\mathrm{\Pi }}_2$ back to their original vertices, $|V(H)|\le |V(H^{\prime })|$, so it suffices to bound the number of vertices in $H^{\prime }$. Recall that $T^{\prime }$ is the set that contains all portals and terminals in $G^{\prime }$, then

where we have used the previously set parameters ${\epsilon }^{\prime }=\epsilon /2f^2$ and ${\epsilon }^{\prime \prime }=(1-1/f^2)\cdot \epsilon$, and the fact that , as $c$ is large enough.

Recall that we sliced $G$ open along $\mathrm{\Pi }$ to obtain $G^{\prime }$, computed a $(1+{\epsilon }^{\prime \prime })$ pattern emulator $H^{\prime }$ for $G^{\prime }$, and then glue $H^{\prime }$ back to obtain $H$. For the purpose of analysis, image that we have also glued $G^{\prime }$ back to obtain $G^{\prime \prime }$. The analysis is complete by the following claims.

Let $G$ be a planar graph on $n$ vertices and let $T$ be its terminals. For any integer $r>1$, a structured $r$-division of $G$ is a collection $𝒢$ of subgraphs of $G$, such that

• $\mathrm{■}$

  $|𝒢|=O(n/r)$;

• $\mathrm{■}$

  the edge sets $\{E(G^{\prime })\mid G^{\prime }\in 𝒢\}$ partitions $E(G)$;

• $\mathrm{■}$

  for each $G^{\prime }\in 𝒢$, $|V(G^{\prime })|\le r$, $|T\cap V(G^{\prime })|=O(1+|T|\cdot r/n)$, and if we call vertices in $G^{\prime }$ that appear in some other graph in $𝒢$ its boundary vertices, then

  • –

    the number of boundary vertices is $O(\sqrt{r})$;

  • –

    in the planar drawing of $G^{\prime }$ induced by the planar drawing of $G$, all boundary vertices lie on $O(1)$ faces.

We use the following lemma in [5] for computing structured $r$-divisions.

We now prove Theorem 1. The algorithm is simply: compute a structured $r$-division $𝒢$ of the input graph $G$, construct cut sparsifiers for graphs $G^{\prime }\in 𝒢$ using Lemma 14, and then glue them together to obtain a cut sparsifier for $G$. It turns out that we need to apply the algorithm several times in order to obtain a near-linear size cut sparsifier, each time with different parameters $r,\epsilon$.