Light Edge Fault Tolerant Graph Spanners

As discussed, our algorithm for constructing a $f$-EFT $k$-spanner is the following. Let $Q$ be the optimal $2f$-EFT connectivity preserver of $G$, i.e., the graph that we are competing with (the weight in the denominator of our lightness definition). We begin by adding $Q$ to the spanner $H$. Then we use the standard greedy algorithm: we consider each other edge $e\in E(G)\setminus Q$ in nondecreasing weight order, and we add $e=\{u,v\}$ to $H$ if there is some set $F_e\subseteq E(H)$ with $|F_e|\le f$ such that ${\text{dist}}_{H\setminus F_e}(u,v)>k\cdot {\text{dist}}_{G\setminus F_e}(u,v)$. We say that $e$ is in a block with each $e^{\prime }\in F_e$, or equivalently that $(e,e^{\prime })$ form a block for each such $e^{\prime }$. Note that $e$ is the first edge of a block at most $|F_e|\le f$ times. The collection of all blocks is called a blocking set.

Next, we explain the relationship to the weighted girth framework from [31]. Standard arguments (first introduced by [14]) can be adapted to our modified algorithm to show that essentially every cycle in $H$ with at most $k+1$ edges must contain two edges that form a block, i.e., the blocks cover all cycles with at most $k+1$ edges. Following a proof from [31], this argument can be adapted to show that they also cover essentially all cycles with “normalized weight” at most $k+1$, i.e., cycles $C$ where $w(C)/{\max }_{e\in C}w(e)$ is at most $k+1$. This is useful because if there were no cycles of normalized weight at most $k+1$ – or, in the language of [31], $H$ has weighted girth $>k+1$ – then by definition $H$ has lightness at most $\lambda (n,k+1)$. So we have a spanner $H$ where cycles of normalized weight at most $k+1$ exist but are blocked, and we know that if there were no such cycles then we have good lightness bounds. So our goal will be to turn $H$ into some other graph $H^{\prime }$ without any cycles of normalized weight at most $k+1$, in a way that allows us to bound the lightness of $H$ using the lightness of $H^{\prime }$.

In the sparsity setting, one of the now-standard ways of going from a graph $H$ where short cycles exist but are blocked to a graph $H^{\prime }$ where there are no short cycles is by subsampling $H$ to get $H^{\prime }$. Informally, by choosing the correct probability, one can often show that no blocks survive in $H^{\prime }$, and thus there cannot be any short cycles and so there are not many edges in $H^{\prime }$. On the other hand, since we obtained $H^{\prime }$ by subsampling $H$ with a known probability, there are not too many more edges in $H$ than in $H^{\prime }$. Thus $H$ cannot have many edges. A natural first attempt is to use the same idea for lightness, but it immediately runs into a serious problem. The connectivity preserver $Q$ itself can have unblocked cycles of low normalized weight, and so if the subsampling does not remove any edges of $Q$ then we cannot hope to get rid of all such cycles. However, if the subsampling does get rid of edges of $Q$, then the min-weight connectivity preserver of the subsampled graph $H^{\prime }$ might be very different from $Q$, making it hard to compare the lightnesses of $H$ and $H^{\prime }$. (Note that this problem does not show up when analyzing sparsity, since the number of edges is not normalized by anything and so it is relatively easy to compare $|E(H)|$ to $|E(H^{\prime })|$).

To get around this, we first observe that if $Q$ happened to be a tree that was disjoint from the blocking set then we would be in good shape: none of the low-normalized-weight cycles would use $Q$, so we could do standard subsampling of $E(H)\setminus Q$ and then include $Q$ deterministically to get a subgraph with high weighted girth where $Q$ still exists. Unfortunately, $Q$ will not be a tree. But suppose that we could find at least $f+1$ disjoint spanning trees in $Q$. Then since each edge $e\in E(H)\setminus Q$ is blocked by at most $f$ other edges (the edges in $F_e$), we can find at least one of these trees which does not contain any edge blocked with $e$. We can then add $e$ to this tree. Once we do this for every $e\in E(H)\setminus Q$, we have a partition of $E(H)\setminus Q$ into $f+1$ disjoint subgraphs with the property that each subgraph contains a spanning tree of $Q$, and no edge in that subgraph includes a block with the spanning tree. So we’re in the setting we want to be in, and we can show that each of these subgraphs has good lightness. Since $Q$ and $H$ are both partitioned across these subgraphs, this implies that we have good lightness overall.

How can we find $f+1$ disjoint spanning trees in $Q$? One very useful tool for finding disjoint spanning trees in graphs is the tree packing theorem of Nash-Williams [46], which implies that it suffices for $Q$ to be $2f+2$-connected. This is close to what we want, except for two issues:

1. 1.

   First, $Q$ is a $2f$-EFT connectivity preserver, which means that if $G$ is $2f+1$-connected (or more) then $Q$ is $2f+1$-connected. We desire $2f+2$-connectivity, so we are off by one from our desired connectivity threshold.

2. 2.

   Second, $G$ need not be $2f+1$-connected at all, and so $Q$ need not even be $2f+1$-connected.

Fortunately, it turns out that we can get around both of these issues via a “doubling trick” and by applying bounds on Steiner Forest packing rather than spanning tree packing. Since $Q$ is a $2f$-EFT connectivity preserver, for any edge $(u,v)\in E(H)\setminus Q$ we know that the pair $(u,v)$ is $2f+1$-connected in $G$, or else we would have to include $(u,v)$ in $Q$. So while $Q$ is not $2f+1$-connected, every pair $u,v$ that are endpoints of an edge in $E(H)\setminus Q$ are $2f+1$-connected in $G$ and thus in $Q$. It turns out that this actually implies that there are $\mathrm{\Omega }(f)$ disjoint forests in $Q$ so that for each $\{u,v\}\in E(H)\setminus Q$, $u$ and $v$ are connected in all of the forests. In other words, we can find $\mathrm{\Omega }(f)$ Steiner forests when the demand pairs are $e\in E(H)\setminus Q$. We would now be done if this $\mathrm{\Omega }(f)$ was $f+1$, but unfortunately it is more like $f/16$  [37]; improving the constant in Steiner forest packing is a fascinating open problem, and the correct bound is not even known for Steiner trees [36, 25].

So we add one more step: we first double every edge of $Q$ to get a multigraph $Q^{\prime }$. Now every $\{u,v\}\in E(H)\setminus Q$ is $4f+2$-connected in $Q^{\prime }$ and, importantly, all degrees are even and thus $Q^{\prime }$ is Eulerian. This turns out to make Steiner Forest packing significantly easier, and optimal bounds are known: it was shown by Chekuri and Shepherd [22] that if all demand pairs $u,v$ are $2k$-connected in an Eulerian graph $G$, then we can find $k$ disjoint Steiner forests in $G$ (and can even do so in polynomial time). This means that we can find $2f+1$ disjoint Steiner forests in $Q^{\prime }$, and thus when interpreted in $Q$ we get $2f+1$ Steiner forests that are not disjoint, but where every edge of $Q$ is in at most $2$ of them.

But this is sufficient for us. Since each edge $e$ is in a block with at most $f$ edges of $Q$, and each edge of $Q$ can appear at most two of $2f+1$ Steiner forests, we get that there must be some Steiner forest which has no edge blocked with $e$, as desired.

To sum up: to bound the $2f$-competitive lightness of $H$, we double every edge of $Q$ and use the Steiner Forest packing in Eulerian graphs result of [22] to find $2f+1$ edge-disjoint Steiner forests, which correspond to $2f+1$ Steiner forests in $Q$ where every edge in $Q$ appears at most twice. Then for every edge $e\in E(H)\setminus Q$ we add it to a Steiner forest which does not contain any of its blocks. Finally, for each of the resulting subgraphs we use subsampling techniques to bound their lightness.

This approach turns out to give a lightness bound of $f\cdot \lambda (n,k+1)$ (see Section 3.3). In order to improve the bound to $f^{1/2}\cdot \lambda (n,k+1)$, we need to be a bit more careful. At a very high level, we allow ourselves to add edges of $E(H)\setminus Q$ to many of the Steiner forests at once, where possible. If it is possible then we get an improved bound, roughly since our previous analysis overcounts multiply-added edges, letting us divide out an additional factor. For edges that cannot be added to many Steiner forests, it turns out the previous subsampling technique can be made more efficient, also giving an improved bound in this other case.

The upper bound in Theorem 12, with a higher competition parameter, has an almost identical proof to Theorem 11. The main difference is that, since we now have that $Q$ is a $(2+\eta )f$-EFT connectivity preserver, if we repeat the above analysis then for any $e\in E(H)\setminus Q$ we can now find ${\mathrm{\Omega }}_{\eta }(f)$ Steiner forests in the forest packing of $Q$ that don’t contain a block with $e$, rather than just $1$. Thus if we add the weights of all of the subgraphs, we are overcounting every edge by a factor of $\mathrm{\Omega }(f)$. When we plug this into the previous calculations, we end up exactly canceling out the $f$-dependence, giving the improved upper bound.

As is well known in the spanners literature (e.g. [1]), it suffices to verify that for any set $F$ of $|F|\le f$ edge faults and any edge $(u,v)\in E(G)\setminus (E(H)\cup F)$, we have ${\text{dist}}_{H\setminus F}(u,v)>k\cdot w(u,v)$. To show this, we first observe that for any such edge we have $(u,v)\notin Q$ (since we add all of $Q$ to $H$), and so we consider $(u,v)$ at some point in the main for-loop of the algorithm. We choose not to add $(u,v)$ to $H$, meaning that for all possible fault sets $F$ we have ${\text{dist}}_{H\setminus F}(u,v)\le k\cdot w(u,v)$. For the rest of the algorithm we only add edges to $F$, and since this property is monotonic in $H$, it will still hold in the final spanner. $◀$

Now we turn to analyzing lightness. When $f=0$, this algorithm produces a spanner $H$ of weighted girth $>k+1$ [31]. For larger $f$, there is not much we can say about the weighted girth of the output spanner, which could be quite small. However, we might intuitively expect the output spanner to be “structurally close” to a graph of high weighted girth. That notion of closeness can be formalized by adapting the blocking set framework, which has been used in many recent papers on fault-tolerant spanners and related objects (see, e.g., [14, 29, 10, 11, 7, 8, 52, 13]).

The following is a tweak on a standard lemma bounding the size of the blocking set of the output spanner; the proof is a straightforward mixture of related lemmas from [14] and [31].

In the main part of the construction, whenever we add an edge $(u,v)\in E(G)\setminus Q$ to the spanner $H$, we do so because there exists a fault set $F_{(u,v)}$ that satisfies the conditional (there might be many possible choices of $F_{(u,v)}$, in which case we fix one arbitrarily). Let

Since each $|F_e|\le f$, we have that $B$ is $f$-capped. To argue its cycle-blocking properties, let $C$ be a cycle as in the lemma statement, with a heaviest edge $(u,v)\notin Q$. When we consider $(u,v)$ in the main loop of the algorithm, just before $(u,v)$ is added to $H$, there exists a $u\rightsquigarrow v$ path through the other edges of the cycle, and so

However, in order to satisfy the conditional and include $(u,v)$ in $H$, we must have that ${\text{dist}}_{H\setminus F_{(u,v)}}(u,v)>k\cdot w(u,v)$. Thus at least one edge $e\in C\setminus \{(u,v)\}$ must be included in $F_{(u,v)}$. So we have $\{(u,v),e\}\in B$, which blocks $C$, completing the proof. $◀$

A subtlety here is that the output spanner $H$ could still have unblocked cycles $C$ of low weighted girth, in the case where the heaviest edge of $C$ is in $Q$ (and so it was added before the main greedy loop of the algorithm), and the edges in $C\setminus Q$ are much lighter. In general, min-weight $f$-EFT connectivity preservers are less well-behaved than min-weight spanning trees, and so situations like this are indeed possible even despite $Q$ being min-weight. We will need to handle these cycles in our analysis in another way (see Lemma 26).

To begin the proof, we recall the classic Nash-Williams tree packing theorem:

The following is a simple corollary. The actual packing that we will use is a bit more complicated, but we give this simpler corollary to build intuition.

Replace every edge of $G$ with two parallel edges, so that it is $2f$-connected. Then consider any vertex partition $𝒫$, and note that (by connectivity) every part must have at least $2f$ outgoing edges. Thus there are at least $f\cdot |𝒫|$ edges between parts. This is even a bit stronger than the condition needed to apply the Nash-Williams theorem, and so by Theorem 22 we can partition $G$ into $f$ edge-disjoint spanning trees. Since we initially doubled the edges of $G$, this means that every original edge participates in at most two spanning trees. $◀$

If the input graph $G$ is $(2f+1)$-connected (and therefore $Q$ is also $(2f+1)$-connected), then this corollary would give the right technical tool. However, in order to avoid assuming any connectivity properties of the input graph, we instead need a generalization. We begin with the following theorem by Chekuri and Shepherd, which gives the appropriate analog in the special case of Eulerian graphs:

We will use the following corollary:

Identical to the previous corollary. Note that when we double edges, every node has even degree, so we guarantee that the graph is Eulerian and so can apply Theorem 24.⁷⁷7Technically this edge-doubling step makes $G$ a multigraph, which is not explicitly mentioned in the Chekuri-Shepherd theorem [22]. However, their proof extends straightforwardly to multigraphs. $◀$

The first step in our analysis of Algorithm 1 is to apply this corollary to $Q$, with parameter $2f+1$, yielding a collection of subtrees $𝒯$.

Our next step is to construct a sequence of four subgraphs $H[T]\supseteq H^{\prime }[T]\supseteq H^{\prime \prime }[T]\supseteq H^{\prime \prime \prime }[T]$ associated to each tree $T\in 𝒯$. In the following let $B$ be an $f$-capped blocking set for $H$ as in Lemma 20.

• $\mathrm{■}$

  (Construction of $H\mathbf{[}T\mathbf{]}$) Consider the edges in $(u,v)\in E(H)\setminus Q$ one at a time. Notice that there cannot exist $2f$ edge faults in $Q$ that disconnect the nodes $u,v$, since otherwise we would need to include the edge $(u,v)$ in $Q$. Thus the node pair $(u,v)$ is $(2f+1)$-connected in $Q$. So the endpoint nodes $u,v$ lie in the same $(2f+1)$-connected component $C$ of $Q$, and by Corollary 25 there exist $2f+1$ trees in $𝒯$ that all span $C$.

  Since $B$ is $f$-capped, there are at most $f$ edges $e^{\prime }$ with $(e,e^{\prime })\in B$. Since each such edge $e^{\prime }$ can be in at most two trees (by Corollary 25), it follows that there exists at least one tree $T\in 𝒯$ for which no such edge $e^{\prime }$ is in $T$ (if there are multiple such trees, choose one arbitrarily). We choose such a tree $T$ and say that it hosts $e$. Then, for all $T\in 𝒯$, let $H[T]$ be the graph that contains $T$ and all edges hosted by $T$.

• $\mathrm{■}$

  (Construction of $H^{\mathbf{\prime }}\mathbf{[}T\mathbf{]}$) For each tree $T$, we construct $H^{\prime }[T]$ by keeping every edge in $T$ deterministically, and keeping every edge in $H\setminus T$ independently with probability $1/f$.

• $\mathrm{■}$

  (Construction of $H^{\mathbf{\prime \prime }}\mathbf{[}T\mathbf{]}$) To construct $H^{\prime \prime }[T]$ from $H^{\prime }[T]$, for every pair $(e,e^{\prime })\in B$ with $e,e^{\prime }\in H^{\prime }[T]$, we delete the first edge $e$, and let $H^{\prime \prime }[T]$ be the remaining subgraph.

• $\mathrm{■}$

  (Construction of $H^{\mathbf{\prime \prime \prime }}\mathbf{[}T\mathbf{]}$) To construct $H^{\prime \prime \prime }[T]$ from $H^{\prime \prime }[T]$, we delete all edges in $T\setminus \text{mst}(H^{\prime \prime }[T])$.

The important properties of these subgraphs are:

Let $C$ be any cycle in $H[T]$ of normalized weight $\le k+1$. We will argue that $C$ does not survive in $H^{\prime \prime \prime }[T]$. There are two cases, depending on whether $C$ has a heaviest edge $(u,v)\notin T$, or whether all heaviest edges in $C$ are in $T$.

In the first case, suppose that there is a heaviest edge $(u,v)\in C,(u,v)\notin Q$. By the properties of the blocking set $B$ from Lemma 20, there is $(e,e^{\prime })\in B$ with $e,e^{\prime }\in C$ and $e\notin T$. It is not possible for both edges $e,e^{\prime }$ to survive in $H^{\prime \prime }[T]$, since if they are both selected to remain in $H^{\prime }[T]$ then we will choose to delete $e$ when we construct $H^{\prime \prime }[T]$. Thus $C$ does not survive in $H^{\prime \prime }[T]$.

In the second case, suppose that all heaviest edges in $C$ are also in $Q$. Suppose that all edges in $C$ survive in $H^{\prime \prime }[T]$. Then at least one of the heaviest edges $(u,v)\in C$ will not be in $\text{mst}(H^{\prime \prime }[T])$ (since otherwise we could exchange it for a lighter edge on $C$). So we will remove $(u,v)$ when we move from $H^{\prime \prime }[T]$ to $H^{\prime \prime \prime }[T]$. $◀$

Every edge in $T$ is included in $H^{\prime \prime }[T]$ deterministically. Every edge $e\in E(H[T])\setminus T$ survives in $H^{\prime \prime }[T]$ iff the following two independent events both occur:

• $\mathrm{■}$

  $e$ is selected to be included in $H^{\prime }[T]$, which happens with probability $1/f$, and

• $\mathrm{■}$

  For all pairs $(e,e^{\prime })\in B$ with $e$ first, the other edge $e^{\prime }$ is not selected to be included in $H^{\prime }[T]$. Since $B$ is $f$-capped, there are at most $f$ such edges $e^{\prime }$ to consider. Additionally, since $T$ hosts $e$, none of these edges $e^{\prime }$ are in $T$ itself. Thus we select them each to be included in $H^{\prime }[T]$ independently with probability $1/f$. Since we have $f$ independent events that each occur with probability $1-1/f$, the probability that none of them occur is at least $1/4$.

Thus each edge $e\in E(H[T])$ survives in $H^{\prime \prime }[T]$ with probability $\mathrm{\Omega }(1/f)$, implying that $𝔼\left[w(H^{\prime \prime }[T])\right]\ge \mathrm{\Omega }\left(\frac{w(H[T])}{f}\right)$. Finally, when we move from $H^{\prime \prime }[T]$ to $H^{\prime \prime \prime }[T]$, we can only possibly delete edges in $T$ and so we delete at most $w(T)$ weight, implying the lemma. $◀$

As in the probabilistic method, there exists a realization of the subgraphs $H^{\prime \prime \prime }[T]$ that satisfies the expected weight inequality in the previous lemma (for all $T$). Rearranging the bound from Lemma 27, we have $w(H[T])\le O(f)\cdot \left(w(H^{\prime \prime \prime }[T])+w(T)\right)$. Using this, we observe that for all trees $T\in 𝒯$, we have

where the last steps follow from the definition of $\lambda$, the fact that $\lambda (n,k+1)\ge 1$, and the previous lemma establishing that $H^{\prime \prime \prime }[T]$ has weighted girth $>k+1$. Thus, to wrap up the proof, we bound:

Follow the previous analysis, but note that our guarantee is now that we have a set of trees $𝒯$ such that (1) every edge is in at most two trees, and (2) for all $(u,v)\in E(G)\setminus Q$, there are $(2+\eta )f+1$ trees in $𝒯$ that span the $(2+\eta )f+1$-connected component that contains $u,v$. Thus, letting $F$ be a fault set that caused us to add $(u,v)$ to the spanner, there are $\mathrm{\Theta }(\eta f)$ of these trees that are disjoint from $F$. We let each of these trees host the edge $(u,v)$. In particular, this means that $(u,v)$ will appear in $\mathrm{\Theta }(\eta f)$ many $H[T]$ subgraphs. From there the analysis continues as before, but our final calculation is:

$◀$

If we don’t wish to harm our competition parameter, we can use a related method to improve the dependence to $f^{1/2}$:

Let us say that an edge $e\in E(H)\setminus Q$ is $Q$-heavy if there are at least $f-f^{1/2}$ different edges $e^{\prime }\in Q$ with $(e,e^{\prime })\in B$. Otherwise, we say that $e$ is $Q$-light. Let $H_{heavy}\subseteq H$ be the subgraph that includes $Q$ and all edges in $E(H)\setminus Q$ are $Q$-heavy, and similarly let $H_{light}\subseteq H$ be the subgraph that includes $Q$ and all edges in $E(H)\setminus Q$ that are $Q$-light. Notice that