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.