Abstract:
Fault tolerant distance preservers are sparse subgraphs that preserve distances between given pairs of nodes under edge or vertex failures. In this paper, we present the first non-trivial constructions of subset distance preservers, which preserve all distances among a subset of nodes S, that can handle either an edge or a vertex fault. - For an n-vertex undirected weighted graph or weighted DAG G = (V,E) and S ⊆ V, we present a construction of a subset preserver with Õ(|S|n) edges that is resilient to a single fault. In the single pair case (|S| = 2), the bound improves to O(n). We further provide a nearly-matching lower bound of Ω(|S|n) in either setting, and we show that the same lower bound holds conditionally even if attention is restricted to unweighted graphs. - For an n-vertex directed unweighted graph G = (V,E) and r ∈ V, S ⊆ V, we present a construction of a preserver of distances in {r} × S with Õ(n^{4/3} |S|^{5/6}) edges that is resilient to a single fault. In the case |S| = 1 the bound improves to O(n^{4/3}), and for this case we provide another matching conditional lower bound. - For an n-vertex directed weighted graph G = (V, E) and r ∈ V, S ⊆ V, we present a construction of a preserver of distances in {r} × S with Õ(n^{3/2} |S|^{3/4}) edges that is resilient to a single vertex fault. (It was proved in [Greg Bodwin et al., 2017] that the bound improves to O(n^{3/2}) when |S| = 1, and that this is conditionally tight.)
