Streaming Algorithms for Network Design

Our first contribution is a general and broadly applicable framework to obtain streaming algorithms with low space and good approximation ratios for SNDP; this is provided in Section 2. This framework applies to both edge and vertex connectivity, as well as an intermediate setting known as element-connectivity. ²²2Here, the vertex set $V$ is divided into two types: reliable ($R$) and non-reliable ($V\setminus R$). Elements denote the set of edges $E$ and the set of non-reliable vertices $V\setminus R$. For $u,v\in R$, a set of $uv$-paths are element-disjoint if they are disjoint on elements. This framework addresses Question 1 and partially resolves Question 2 affirmatively. All the results below use $\tilde{O}(k^{1-1/t}{n}^{1+1/t})$-space for vertex-connectivity and element-connectivity problems, and $\tilde{O}(k^{1/2-1/(2t)}{n}^{1+1/t}+kn)$-space for edge-connectivity problems, where $k$ is the maximum connectivity requirement and $t$ is a parameter that allows for an approximation vs. space tradeoff. ³³3When $t$ is an even integer, the space used is a factor of $k^{1/(2t)}$ more than when $t$ is odd. The results stated in this section assume that $t$ is an odd integer.

• $\mathrm{■}$

  For EC-SNDP, the framework yields $8t$-approximation, improving upon the $O(t\log k)$-approximation from [45]. For an $O(t)$-approximation, the space bound of our algorithm is off by only a factor of $k^{1/2-1/(2t)}$ from the known lower bound. These bounds also hold for element-connectivity, providing the first such results for this variant.

• $\mathrm{■}$

  For VC-SNDP, the framework yields an $O(tk)$-approximation.

• $\mathrm{■}$

  For VC-SNDP, the framework yields an $O(\beta t)$-approximation where $\beta$ is the integrality gap of the natural LP relaxation. Using this, we obtain improved algorithms for several important special cases including $k$-VCSS and $k$-VC-CAP.

There is substantial literature on network design; here we briefly discuss some relevant literature. EC-SNDP admits a $2$-approximation via the seminal work on iterated rounding by Jain [44] and this has been extended to ELC-SNDP [35, 21]. We note that the best known approximation for Steiner Forest, the special case with connectivity requirements in $\{0,1\}$, is $2$. Steiner tree is another important special case, and for this there is a $(\ln 4+ϵ)$-approximation [14]. Even for $2$-ECSS the best known approximation is $2$, although better bounds are known for the unweighted case. Recently there has been exciting progress on $k$-EC-CAP, starting with progress on the special case of weighted TAP (tree augmentation problem which corresponds to $k=1$). For all $k$, $k$-EC-CAP admits a ($1.5+ϵ)$-approximation [69] – see also [67, 68, 13, 15, 37]. In contrast to the constant factor approximation results for edge-connectivity, the best known approximation for VC-SNDP is $O(k^3\log n)$ due to Chuzhoy and Khanna [22]. Moreover, even for the single-source setting it is known that the approximation ratio needs to depend on $k$ for sufficiently large $k$ [16]. The single-source problem admits an $O(k^2)$-approximation [61, 63] and subset $k$-connectivity admits an $O(k{\log }^{2}k)$-approximation [54]. Several special cases have better approximation bounds. When $k\le 2$, VC-SNDP admits a $2$-approximation [35, 21] which also implies that $k$-VCSS for $k=2$ and $k$-VC-CAP for $k=1$ admit a $2$-approximation. For $k$-VCSS a $(4+ϵ)$-approximation is known when $n$ is large compared to $k$ [65, 20]. For smaller value of $k\le 6$ improved bounds are known – see [64]. These are also the best known bounds for $k$-VC-CAP when $n$ is large compared to $k$. For large $k$, $k$-VC-CAP and $k$-VCSS admit an $O(\log \frac{n}{n-k})$ and $O(\log k\log \frac{n}{n-k})$-approximation respectively with more precise bounds known in various regimes [64]. We note that many of the approximation results (but not all) are with respect to a natural cut-cover LP relaxation. This is important to our analysis since some of our results are based in exploiting the integrality gap of this LP relaxation. Many improved results are known for special cases of graphs including unweighted graphs, planar and graphs from proper minor-closed families, and graphs arising from geometric instances. We focus on general graphs in this work.

Graph problems in the streaming model have been studied extensively, particularly in the context of compression methods that reduce the graph size and preserve connectivity within a factor of $t$ (i.e., spanners) [31, 8, 30] or approximate cuts within a $(1+ϵ)$ factor (i.e., cut sparsifiers and related problems) [1, 51, 48, 49]. These problems have also been widely explored in the dynamic streaming model, where edges are both inserted and deleted. While graph sketching approaches have sufficed to yield near-optimal algorithms for sparsifiers [2], the state-of-the-art for spanners in dynamic streams remained multi-pass algorithms until recently [2, 47]. Filtser et al. [34] developed the first single-pass algorithm for $\tilde{O}(n^{2/3})$-spanners using $\tilde{O}(n)$ space in dynamic streams. Though this result has a large approximation factor, Filtser et al. conjectured that it may represent an optimal trade-off.

Another line of research related to our work is testing connectivity in graph algorithms. This problem has been studied for both edge-connectivity and vertex-connectivity [31, 71, 66], as well as in dynamic settings [2, 23, 40, 7]. Specifically, $k$-connectivity for both edge- and vertex-connectivity can be tested using $\tilde{O}(nk)$ space even in dynamic streams [2, 7].

Finally, for the problem of $k$-ECSS, [45] designed a $k$-pass algorithm within the augmentation framework [39] that finds an $O(\log k)$-approximate solution using $\tilde{O}(nk)$ space.

Due to space constraints, this version of the paper serves as an extended abstract. Please see the full version [17] for more detailed description of technical details and related work.

The standard greedy algorithm for $f$-FT spanners runs in time $O(n^f)$ and this is not computationally efficient for large values of $f$. The study of polynomial-time constructions of such spanners is an active research question [29, 10, 11]. In particular, the following polynomial-time constructions can be implemented in the streaming setting. In all the methods described, the key modification is to replace the naïve $O(n^f)$-time $(u,v)$ test (i.e., checking whether there exists a set of f edges or vertices whose removal increases the distance between $u$ and $v$ in the remaining subgraph to at least $2t$) with a polynomial-time $(u,v)$ test.

• $\mathrm{■}$

  VFT: Bodwin, Dinitiz and Robelle [10] proposed a randomized implementation of the greedy approach for $f$-VFT $(2t-1)$-spanners. In their method, when testing whether to add an edge $(u,v)$, the algorithm randomly samples $\mathrm{\Theta }(\log n)$ induced subgraphs of the current spanner. Each subgraph includes $u,v$, and each of the remaining vertices is included independently with probability $1/(2f)$. Then, the edge $(u,v)$ is added to the spanner if, in at least $1/4$ fraction of the sampled subgraphs, the distance between $u$ and $v$ exceeds $2t-1$. They show that this algorithm succeeds with high probability. It is simple to see that this can be implemented in the streaming setting in space that is proportional to the size of the spanner. Hence, it is possible to construct an $f$-VFT $(2t-1)$-spanner of optimal size, i.e., $\tilde{O}(f^{1-1/t}{n}^{1-1/t})$, in polynomial time in the streaming model, that succeeds with high probability.

• $\mathrm{■}$

  EFT: Dinitz and Robelle [29] provided a simple polynomial-time construction of $f$-EFT $(2t-1)$-spanners with slightly increased size complexity, i.e., $O(t{f}^{1-1/t}{n}^{1+t})$, which can be implemented efficiently in the streaming model too. Specifically, in their approach, when testing whether to add an edge $(u,v)$, they perform $f$ iterations as follows: starting with an initially empty set of edges $F$, in each iteration they attempt to find a path of length at most $(2t-1)$ between $u$ and $v$ in $S\setminus F$ and add it to $F$, where $S$ is the current spanner. If such a path exists, it is added to $F$. If, in any iteration, no such path is found in $S\setminus F$, then the edge $(u,v)$ is added to the spanner $S$. Otherwise, it is not added. Later, Bodwin, Dinitz, and Robelle [11] provided an improved analysis of the same (polynomial time) algorithm, achieving size bounds only slightly worse than those of the greedy approach with an exponential-time $(u,v)$ test. Their result constructs $f$-EFT $(2t-1)$-spanners of size $O(t^{2.5}{f}^{1/2-1/(2t)}{n}^{1+1/t}+t^{2}fn)$ for odd $t$. For even $t$, the spanner size is $O(t^{2.5}{f}^{1/2}{n}^{1+1/t}+t^{2}fn)$.

In all the described algorithms, we perform an exponential time exhaustive search, by enumerating all possible solutions, on the constructed spanner to find an optimal solution after the stream terminates. The spanner effectively serves as a coreset for the problem. Since most of the problems considered in this paper are NP-hard, one could instead run known polynomial time approximation algorithms in the offline setting. We discuss some such approximation algorithms of interest.

The best known approximation for EC-SNDP is a 2-approximation via iterated rounding [44]. However, this requires exactly solving the cut-based LP; it is unclear if this can be done in linear space, especially given that this LP is exponentially sized. There is a primal-dual 2-algorithm for the connectivity augmentation problem [70]; this can be implemented in linear space. While the algorithm does not directly solve the LP, the analysis shows that it is a 2-approximation with respect to the optimal fractional solution. This can be repeatedly applied to obtain an $O(\log k)$-approximation (where $k$ is the maximum connectivity requirement) for EC-SNDP [39]. For vertex-connectivity, The best known approximation for VC-SNDP employs a reduction to element connectivity. Given an $\alpha$-approximation for ELC-SNDP that uses $f(m)$ space, one can obtain a $O(\alpha k^3\log n)$-approximation in $O(m+f(m))$ space [22]. Some algorithms for special cases of VC-SNDP (such as single-source, $k$-VC-CAP, etc.) may be modified to run in linear space; we omit details for brevity and refer the reader to related work discussed in Section 1.2.

Combining the two parts, we achieve the following efficient streaming algorithms, where $S$ is the space usage for the corresponding streaming problem (i.e. $S=k^{1-1/t}\cdot n^{1+1/t}$ for vertex-connectivity instances, and $S=k^{1/2-1/(2t)}\cdot n^{1+1/t}+kn$ for edge-connectivity instances):

• $\mathrm{■}$

  Integral Solution Approach. If there exists a polynomial time $\alpha$-approximation algorithm for the SNDP problem with space complexity $g(m)$, where $m$ is the size of the input graph, our framework returns an $O(\alpha tk)$-approximate solution in polynomial time, using $\tilde{O}(S+g(S))$ space.

• $\mathrm{■}$

  Fractional Soultion Approach. If there exists a polynomial time algorithm for the SNDP problem that returns an integral solution within an ${\alpha }_{\mathrm{fr}}$-factor of the optimal fractional solution to the cut-based LP relaxation of the problem, with space complexity $g(m)$ (where $m$ is the size of the input graph), then our framework returns an $O({\alpha }_{\mathrm{fr}}\cdot t)$-approximate solution in polynomial time, using $\tilde{O}(S+g(S))$ space.

We want to show that for all $a\in V$, $(V,E\cup \text{SOL})\setminus \{a\}$ is connected. Fix $a\in V$. Since OPT is feasible, it suffices to show that for all $uv\in \text{OPT}$ with $u,v\ne a$, there exists a $u$-$v$ path in $E\cup \text{SOL}$ that does not use $a$. Fix $uv\in \text{OPT}$. If the (unique) $u$-$v$ path in $E$ does not contain $a$, then we are done. Thus we assume $a$ is on the $u$-$v$ tree path. We case on whether or not $a$ is the $LCA$ of $u$ and $v$. Let $b=LCA(u,v)$. Let $u^{\prime },v^{\prime }\in C(b)$ be the children of $b$ such that $u\in G_{u^{\prime }}$ and $v\in G_{v^{\prime }}$.

• $\mathrm{■}$

  Case 1: (see Fig 3) Suppose $a=b$. If $u^{\prime }$ or $v^{\prime }$ are not marked as “good”, then $u^{\prime }$ and $v^{\prime }$ correspond to separate supernodes of $C^{\prime }(a)$ and thus $G_{u^{\prime }}$ and $G_{v^{\prime }}$ must be connected via $T_a^{\prime \prime }$. $G_{u^{\prime }}$ and $G_{v^{\prime }}$ remain connected despite the deletion of $a$, so $u$ and $v$ are connected via $T_a^{\prime \prime }$.

  Suppose instead both $u^{\prime }$ and $v^{\prime }$ are marked as “good”. Since $G_{u^{\prime }}$ is good, there must be some link $e_u\in \text{OPT}[G_{u^{\prime }},G\setminus G_a]$. Let $u^{\prime \prime }$ be the vertex incident to $e_u$ in $G_{u^{\prime }}$, and let $j$ be the weight class of $e_u$. Then $L_{u^{\prime \prime }}(j)$ must have an endpoint in $G\setminus G_a$, since . Furthermore, $L_{u^{\prime \prime }}(j)\in \text{SOL}$, since $e_u\in \text{OPT}$. Similarly, there must be some $v^{\prime \prime }\in G_{v^{\prime }}$ such that $L_{v^{\prime \prime }}\cap \text{SOL}$ contains a link with one endpoint in $G\setminus G_a$. Since $G\setminus G_a$ remains connected despite the deletion of $a$, we obtain our desired $u$-$v$ path.

• $\mathrm{■}$

  Case 2: (see Fig 3) If $a\ne b$, then $a$ is either in $G_{u^{\prime }}$ or in $G_{v^{\prime }}$. Suppose without loss of generality that $a\in G_{u^{\prime }}$; the other case is analogous. Let $j$ be the weight class of $uv$. Then ; the first inequality holds since $v\in G\setminus G_b$. Thus $L_u(j)$ has one endpoint in $G\setminus G_a$. Furthermore, $L_u(j)\in \text{SOL}$ since $uv\in \text{OPT}$. Since $G\setminus G_a$ remains connected despite the deletion of $a$, this gives us our desired $u$-$v$ path in $E\cup \text{SOL}$.