Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity

The “$s$-$t$ variant” of this problem has been extensively studied in recent years. Here, a query consists of a triplet $(s,t,F)$, and it is required to determine if $s,t$ are connected in $G-F$. The study of $f$-FT $s$-$t$ connectivity labeling was initiated by Dory and Parter [23] with subsequent works in [32, 41, 42, 37], rendering it reasonably well-understood by now: it is known to admit very succinct labels of only $\mathrm{poly}(f,\log n)$ bits, either with edge failures or with vertex failures; we refer to [37] for a detailed presentation of the state-of-the-art bounds.

Parter, Petruschka and Pettie [42] have proposed the “global connectivity” variant, where the query consists only of $F$, and it is required to determine if $G-F$ is a connected graph. Unlike with $s$-$t$ connectivity, the global variant turns out to behave very differently with edge failures ($F\subseteq E$) or with vertex failures ($F\subseteq V)$. Essentially all known labeling schemes for the $s$-$t$ connectivity variant under edge failures [23, 32, 37] also solve the global variant en route, hence the latter also admits succinct $\mathrm{poly}(f,\log n)$-bit labels. However, in case of vertex failures, it was shown in [42] that polynomial dependency in $f$ is impossible, and their lower bound was improved to $\mathrm{\Omega }(n^{1-1/f}/f)$ by Long, Pettie and Saranurak [37]. Very recently, Jiang, Parter and Petruschka [33] gave a nearly matching upper bound by providing a construction of $f$-FT global connectivity labels of $n^{1-1/f}\cdot \mathrm{poly}(f,\log n)$ bits, essentially settling the problem.

In this work, we study the natural generalization of the problem to Steiner connectivity. In this variant, the graph $G=(V,E)$ comes with a (fixed) subset of designated vertices $U\subseteq V$ called terminals. Given a query $F\subseteq V\cup E$ of up to $f$ faulty vertices/edges, it is required to report if $F$ is a $U$-Steiner cut in $G$, i.e., if there is a pair of disconnected terminals in $G-F$. Note that $U$ is fixed and not a part of the query, so we only get to see the labels of $F$.¹¹1If we also get the labels of $U$, we can just use the $\mathrm{poly}(f,\log n)$-bit labels of the $s$-$t$ variant, and apply $|U|-1$ pairwise connectivity queries (between one terminal in $U$ to all the others) in $G-F$. We call this variant $f$-FT Steiner connectivity labeling scheme.

We first note that the lower bound for the global connectivity variant of [37] immediately yields a lower bound for the Steiner setting as well:²²2Construct the lower bound instance of [37] on $k$ vertices set as terminals, and add $n-k$ isolated vertices.

Our technical contribution is providing a nearly matching upper bound which is optimal up to $\mathrm{poly}(f,\log n)$ factors, hence generalizing the result of [33] (recovered when $U=V$):

The $f$-FT Steiner connectivity labeling scheme of Theorem 2 supports any query $F\subseteq V\cup E$ of vertices and edges with $|F|\le f$. However, the challenge lies entirely in the case of vertex failures, i.e., $F\subseteq V$: proving Theorem 2 for this case implies also the general case. Indeed, we can construct a new instance $(G^{\prime },U)$ where $G^{\prime }$ is obtained from $G$ by splitting each edge $e$ of $G$ by a new middle $v_e$, so the failure of $e$ in $G$ is equivalent to the failure of $v_e$ in $G^{\prime }$ (in terms of affect on connectivity between original vertices).

As for the case of only edge failures $F\subseteq E$, much like in the global connectivity variant, it behaves very differently and admits labels of $\mathrm{poly}(f,\log n)$ bits, implicit by known constructions of $f$-FT connectivity labels for pairwise connectivity queries (the standard $s$-$t$ variant in the literature). Specifically, both the labels of [23] based on linear graph sketches and its derandomized version in [32] are straightforward to augment to answer Steiner connectivity queries,³³3These are based on fixing some spanning tree $T$ for $G$, and reconnecting the connected components of $T-F$ to obtain those of $G-F$. Augment the label of each tree edge with the number of terminals in the subtree below it. Then we can invoke a similar strategy to the sketch computation in [23, 32] to determine the number of terminals in each component of $T-F$, and hence also of $G-F$. and other constructions in [23, 37] seem plausibly amenable to such augmentations as well. In light of the discussions above, in the rest of the paper we will only consider the case of vertex failures, i.e., queries are of the form $F\subseteq V$ with $|F|\le f$.

We mention that providing “Steiner generalizations” that interpolate between the two extreme scenarios of the terminal set ($|U|=n$ and $|U|=2$) is a common objective in various algorithmic and graph-theoretic problems, such as computing Steiner mincut [22, 17, 29, 20], data structures for Steiner mincuts [21, 22, 9] and minimum+1 Steiner cuts [11], sensitivity oracles for Steiner mincuts [10, 11], Steiner connectivity augmentation and splitting-off [16] and construction of cactus graphs for compactly storing and characterizing Steiner mincuts [22, 29].

FT connectivity labeling schemes can be seen as distributed versions of connectivity oracles under failures, which are centralized data structures designed to answer the same kind of queries. These have been extensively studied especially in the $s$-$t$ variant, with both edge faults [43, 24, 28] and vertex faults [24, 47, 38, 45, 36, 39]. Much like with labeling schemes, in the global variant of connectivity oracles, vertex failures require much larger complexity than edge failures, as was first observed by Long and Saranurak [38]. Very recently, Jiang, Parter and Petruschka [33] provided almost-optimal oracles for global connectivity under vertex failures, and their approach seems plausible to extend also to the Steiner variant.

Construct an auxiliary graph $G^{\prime }$ from $G$ by adding a new vertex $z$ and adding an edge $(z,u)$ for every terminal $u\in U$. Let ${\mathrm{\ell }}^{\prime }(\cdot )$ be the labels computed by the algorithm of Theorem 3 on $G^{\prime }$, and define $\overline{\mathrm{\ell }}(v):=({\mathrm{\ell }}^{\prime }(v),{\mathrm{\ell }}^{\prime }(z))$. Now, let $F\subseteq V$ with $|F|\le f$ and $x\in V$. Note that there exists some $u\in U$ which is connected to $x$ in $G-F$ iff $x,z$ are connected in $G^{\prime }-F$. The $\overline{\mathrm{\ell }}(\cdot )$-labels of $F\cup \{x\}$ contain all ${\mathrm{\ell }}^{\prime }(\cdot )$-labels of $F\cup \{x,z\}$, so we can use them to determine if the latter condition holds. $◀$

We first introduce a somewhat technical lemma. Roughly speaking, in terms of the high-level intuition of Section 1.1, it serves to treat the all-high-degree case. The idea is to store explicit information for some relatively small collection of vertex-subsets (of “high-deg vertices”, see Section 1.1), such we have the information on $K\subseteq F$, we can determine if $K$ itself already separates $U-F$, which implies that $F$ is a Steiner cut.

Let $C_1,\mathrm{\dots },C_p$ be the connected components of $G-K$ that contain some terminal, and denote $U_i=C_i\cap U$, where w.l.o.g. $|U_1|\le \mathrm{\cdots }\le |U_p|$. Our goal is that given $\widehat{\mathrm{\ell }}(K)$ and any $F\subseteq V$, $|F|\le f$, we can decide if at least two sets in $\{U_i-F\mid 1\le i\le p\}$ are non-empty.

Suppose there exists some $q$ such that ${\sum }_{i=1}^q|U_i|>f$ and ${\sum }_{i=q+1}^p|U_i|>f$. Then for every $F\subseteq V$ with $|F|\le f$ there is one non-empty set in $\{U_i-F\mid i\le q\}$ and another in $\{U_i-F\mid i\ge q+1\}$. Thus, we just indicate this situation in $\widehat{\mathrm{\ell }}(K)$ and always answer YES.

Assume now that no such $q$ exists.

• $\mathrm{■}$

  If $|U_p|>f$: Then , and we let $\widehat{\mathrm{\ell }}(K)$ store $U_1,\mathrm{\dots },U_{p-1}$ (and indicate that $|U_p|>f$). This suffices as for every $F\subseteq V$ with $|F|\le f$ we know that $U_p-F\ne \mathrm{\varnothing }$, so we only need to decide if $\{U_i-F\mid 1\le i\le p-1\}$ has a non-empty set.

• $\mathrm{■}$

  If $|U_p|\le f$: We assert that the sum ${\sum }_{i=1}^p|U_i|$ is at most $3f$. Indeed, if it is more than $f$, let $q$ be maximal such that ${\sum }_{i=q+1}^p|U_i|>f$. Then ${\sum }_{i=1}^q|U_i|\le f$, ${\sum }_{i=q+2}^p|U_i|\le f$ (by maximality), and $|U_{q+1}|\le |U_p|\le f$. Thus, we just let $\widehat{\mathrm{\ell }}(K)$ store all of $U_1,\mathrm{\dots },U_p$.

$◀$

Our label construction crucially relies on a graph decomposition algorithm of Duan-Pettie [24] (as explained in Section 1.1). This algorithm is a recursive version of the Fürer-Raghavachari [25] algorithm for finding a Steiner tree with smallest possible maximum degree, up to $+1$ error. The Duan-Pettie decomposition utilizes the structural properties of the Fürer-Raghavachari tree (rather than its strong approximation guarantee). In the following, a Steiner forest means a forest in the graph where each pair of connected terminals (in the graph) is also connected in the forest.

In the following we assume that $f\ge 2$, as Theorem 2 is trivial when $f=1$: the label of vertex $x$ just stores a single bit indicating whether $\{x\}$ is a Steiner cut.

Our first step is to invoke $\mathrm{𝖣𝖾𝖼𝗈𝗆𝗉}(G,U,r:={|U|}^{1-1/f}+2)$ of Theorem 6; let $(T,B)$ be the output. For every $x\in V$, we choose an arbitrary terminal $u_x\in U$ such that $x,u_x$ are connected in $G-B$ (where $u_x:=⟂$, i.e., a null value, if there is no such terminal). Next, we construct the $\mathrm{\ell }(\cdot )$-labels and $\overline{\mathrm{\ell }}(\cdot )$-labels of Theorems 3 and 4; for every $v\in V$, define ${\mathrm{\ell }}^{\ast }(v):=(v,\mathrm{\ell }(v),\overline{\mathrm{\ell }}(v))$. Finally, the $L(\cdot )$ labels are constructed as follows:

The label length analysis is rather straightforward, given in detail in the following claim.

By Theorem 3, Lemma 4 and Lemma 5 each ${\mathrm{\ell }}^{\ast }(\cdot )$-label or $\widehat{\mathrm{\ell }}(\cdot )$-label consists of $\mathrm{poly}(f,\log n)$ bits, so we show that only $O({|U|}^{1-1/f})$ such labels are stored in $L(x)$. The first four lines only store $O(|B|)$ such labels, and $|B|\le |U|/(r-2)={|U|}^{1/f}$ by the properties of $\mathrm{𝖣𝖾𝖼𝗈𝗆𝗉}(G,U,r)$ in Theorem 6). As we assume $f\ge 2$, ${|U|}^{1/f}\le {|U|}^{1-1/f}$, so this is within budget. If $x\notin B$, then, line 6 stores ${\mathrm{\ell }}^{\ast }(y)$ for each neighbor $y$ of $x$ in $T-B$, which are at most $r=O({|U|}^{1-1/f})$ again by Theorem 6. Next suppose $x\in B$. The number of sets $K\subseteq B$ s.t. $x\in K$ and $|K|\le f$ can be bounded by

(we used $\left(\genfrac{}{}{0pt}{}{n}{k}\right)\le {(n/k)}^k$ for $1\le k\le n$, ${\sum }_{k=1}^{\mathrm{\infty }}{(e/k)}^k$ is convergent, and $|B|\le {|U|}^{1/f}$). Thus, lines 8 and 9 store $O({|U|}^{1-1/f})$ $\widehat{\mathrm{\ell }}(\cdot )$-labels.

Note that constructing the ${\mathrm{\ell }}^{\ast }(\cdot )$ labels for all vertices takes polynomial time by Theorem 3 and Lemma 4. Also, we only need to construct $\widehat{\mathrm{\ell }}(K)$ labels for sets $K\subseteq B$ such that $x\in B$ and $|K|\le f$ (or such that $K=\mathrm{\varnothing }$), and there are only $O({|U|}^{1-1/f})$ such sets $K$ by the arguments above; constructing each $\widehat{\mathrm{\ell }}(K)$ takes polynomial time by Lemma 5. $\mathrm{⊲}$

The pseudo-code for the query algorithm is given in the following Algorithm 2, designed to return YES if the query $F$ is a Steiner cut, and NO otherwise.

We now provide the implementation details:

• $\mathrm{■}$

  Line 2 is executed using $\widehat{\mathrm{\ell }}(K)$ of Lemma 5 (and the names of the vertices in $F$, given in their labels). If $K=F\cap B$ is non-empty, we can find $\widehat{\mathrm{\ell }}(K)$ in the label $L(x)$ of some $x\in F\cap B$. Otherwise, $\widehat{\mathrm{\ell }}(K)$ is stored in $L(x)$ for every $x\in F$.

• $\mathrm{■}$

  Line 4 is executed by using the $\overline{\mathrm{\ell }}(\cdot )$-labels of the vertices in $S\cup F$ (which appear in their ${\mathrm{\ell }}^{\ast }(\cdot )$-labels). For every $w\in S$, we use $\overline{\mathrm{\ell }}(w)$ and $\{\overline{\mathrm{\ell }}(x)\mid x\in F\}$ to decide if $w$ is connected to some $u\in U$ in $G-F$, which is possible by Lemma 4.

• $\mathrm{■}$

  Line 8 is executed using the $\mathrm{\ell }(\cdot )$-labels of $w^{\ast },w$ and $F$ (which appear in their ${\mathrm{\ell }}^{\ast }(\cdot )$-labels), which enable to determine if $w^{\ast },w$ are connected in $G-F$ by Theorem 3.

We need to show that YES is returned if and only if $F$ is a Steiner cut, namely $F$ separates $U$ in $G$. The soundness direction (‘only if’) is trivial:

If YES was returned in line 2, then $F$ has a subset $K$ which separates two terminals in $U-F$, so these are also separated by $F$. Thus, $F$ is a Steiner cut.

Otherwise, YES was returned in line 8, so there are $w^{\ast },w\in W$ disconnected in $G-F$. By definition of $W$ (line 4 of Algorithm 1), there exists terminals $u^{\ast },u\in U$ such that $u^{\ast },w^{\ast }$ and $u,w$ are connected pairs in $G-F$. Thus, $u^{\ast },u$ are two terminals disconnected in $G-F$, so $F$ is a Steiner cut. $\mathrm{⊲}$

Next, we address the completeness (‘if’) direction:

Let us first consider the trivial case when $K=F\cap B$ separates $U-F$ in $G$. Then Algorithm 2 returns YES in line 2 as needed. Henceforth, we assume that $F$ satisfies the following property:

• (P1)

  $F\cap B$ does not separate $U-F$ in $G$.

Note that given Property (P1), the only possible place where Algorithm 2 can return YES is in line 8, so we aim to show that this is indeed the case. We will crucially use Property (P1) later on in the proof.

Let $u,u^{\prime }\in U$ be two terminals disconnected in $G-F$, which exists as $F$ is a Steiner cut. We will show there exists $w,w^{\prime }\in W$ such that (i) $u,w$ are connected in $G-F$ and (ii) $u^{\prime },w^{\prime }$ are connected in $G-F$. Let us argue why this suffices to complete the proof. First, this clearly implies that $W\ne \mathrm{\varnothing }$. Second, one of $w,w^{\prime }$ must be disconnected from $w^{\ast }$ in $G-F$, as otherwise $w,w^{\prime }$ would be connected in $G-F$, so by (i) and (ii) we get that $u,u^{\prime }$ are also connected in $G-F$, but this is a contradiction. Therefore, line 8 of Algorithm 2, when executed with either $w$ or $w^{\prime }$ must return YES as required.

We thus focus on showing the existence of $w\in W$ which is connected to $u$ in $G-F$ (and the proof for $w^{\prime }$ and $u^{\prime }$ is symmetric). Let $C_u$ be the connected component of $u$ in $G-F$. Recall the definitions of $S$ and its subset $W$ from lines 3 and 4 of Algorithm 2. Note that every vertex $w\in C_u\cap S$ is automatically in $W$, since it belongs to $S$ and is connected to the terminal $u$ in $G-F$. So, our goal is simply to show that $C_u\cap S\ne \mathrm{\varnothing }$, or in other words, that the ${\mathrm{\ell }}^{\ast }(\cdot )$-label of some vertex in $C_u$ is stored in some $L(x)$ of $x\in F$.

Again, there is a trivial case: if $C_u\cap B\ne \mathrm{\varnothing }$ then we are done, because $\{{\mathrm{\ell }}^{\ast }(b)\mid b\in B\}$ is stored in every $L(x)$ of $x\in F$ (line 3 of Algorithm 1), so $B\subseteq S$. Thus, we assume that:

• (P2)

  The connected component $C_u$ of $u$ in $G-F$ does not intersect $B$.

In fact, the inclusion of the ${\mathrm{\ell }}^{\ast }(\cdot )$-labels of $B$ in every label $L(x)$ is precisely aimed at enforcing Property (P2).

Our next step is to “capitalize on” properties (P1), (P2), and the important property that $T-B$ is a Steiner forest for $U-B$ in $G-B$ (guaranteed by Theorem 6). Consider the set $N_G(C_u)$ of all vertices outside $C_u$ that are adjacent to $C_u$ in $G$. Note that, as $C_u$ is a connected component in $G-F$, we have $N_G(C_u)\subseteq F$. Observe that $N_G(C_u)$ separates $U-F$ in $G$, as $u,u^{\prime }\in U-F$ with $u\in C_u$ and $u^{\prime }\notin C_u$. Thus, by Property (P1), it must be that $N_G(C_u)⊈F\cap B$. Hence, there exists some $x\in N_G(C_u)\cap (F-B)$. Now, using Property (P2), we see that all vertices in $C_u\cup \{x\}$ are connected in $G-B$, so $u$ is connected to $x$ in $G-B$. Recall that the terminal $u_x\in U$ is also (by definition) connected to $x$ in $G-B$. (Note that $u_x$ exists since $x$ is connected to the terminal $u$ in $G-B$.) Hence, $u,u_x$ are connected in $G-B$, and thus also in $T-B$. This is the crux for finishing the proof in the following argument. See Figure 1 for an illustration.

Observe that $u_x\in S$, since ${\mathrm{\ell }}^{\ast }(u_x)$ is stored in $L(x)$ (line 2 of Algorithm 1). So, if $u,u_x$ are connected in $G-F$, then $u_x\in C_u\cap S$ and we are done. Otherwise, the path in $T-B$ between $u$ and $u_x$ must go through $F$. Let $x^{\prime }\in F$ be the vertex closest to $u$ on this path, and let $w$ be its neighbor in the direction of $u$ on the path. (It might be that $x^{\prime }=x$.) Then the subpath between $u$ and $w$ avoids $F$, so $w\in C_u$. Also, $x^{\prime }\notin B$ and $(x^{\prime },w)$ is an edge of $T-B$, hence ${\mathrm{\ell }}^{\ast }(w)$ is stored in $L(x^{\prime })$ (line 6 of Algorithm 1), so $w\in S$. Namely, we have shown that $C_u\cap S\ne \mathrm{\varnothing }$, and the proof is concluded. $\mathrm{⊲}$

Theorem 2 follows immediately from the combination of Claim 7, Claim 9 and Claim 10.