Fault-Tolerant Spanners for General Graphs

by Shiri Chechik, Michael Langberg, David Peleg and Liam Roditty.

Oded's comments

I assume that there are other examples of the following issue, but none occurs to me right now. The issue is that the algorithm works by invoking some algorithm on many related inputs (in this case the subgraph obtained by remviong $f$ vertices) while using the same coin tosses in the various invocations. That is, the analysis benefits from the fact that some random choices are the same in all these invocations. (I vaguely recall the same occuring with respect to invocations of some oracles that relate to local queries, but the current case seems different.)

In the case of edges omission, the construction involves an overhead factor that equals the number of omissions, which is optimal. For vertex omissions the overhead is a factor of $k^{f+2}\log n$, where $f$ is the number of omitted vertices and $n$ is the total number of vertices.

The original abstract

The idea of spanners is that for certain algorithmic purposes, instead of using the entire graph, it is sufficient to use a sparser subgraph that closely approximates the distances of the original graph. Formally, a subgraph $H$ is a $k$-spanner of $G$ if for every two vertices their distance in $H$ is at most $k$ times their distance in the original graph $G$. In the fault-tolerant settings, we would like to find a sparse spanner of $G$ which remains a ``good" spanner even when some of the vertices fail. We show how to construct sparse fault-tolerant spanners for general graphs. Our construction is based on the approximate distance oracle construction of Thorup and Zwick (2005). In addition, we show an extremely simple algorithm for constructing fault-tolerant spanners which are resilient to edge failures.

Back to list of Oded's choices.