Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and SubpathsThe restoration lemma is a classic result by Afek, Bremler-Barr, Kaplan,
Cohen, and Merritt [PODC '01], which relates the structure of shortest paths in
a graph $G$ before and after some edges in the graph fail. Their work shows
that, after one edge failure, any replacement shortest path avoiding this
failing edge can be partitioned into two pre-failure shortest paths. More
generally, this implies an additive tradeoff between fault tolerance and
subpath count: for any $f, k$, we can partition any $f$-edge-failure
replacement shortest path into $k+1$ subpaths which are each an
$(f-k)$-edge-failure replacement shortest path. This generalized result has
found applications in routing, graph algorithms, fault tolerant network design,
and more.
Our main result improves this to a multiplicative tradeoff between fault
tolerance and subpath count. We show that for all $f, k$, any $f$-edge-failure
replacement path can be partitioned into $O(k)$ subpaths that are each an
$(f/k)$-edge-failure replacement path. We also show an asymptotically matching
lower bound. In particular, our results imply that the original restoration
lemma is exactly tight in the case $k=1$, but can be significantly improved for
larger $k$. We also show an extension of this result to weighted input graphs,
and we give efficient algorithms that compute path decompositions satisfying
our improved restoration lemmas.
arxiv.org