2026-08-11T09:40:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12422 2024-03-06T10:50:05Z ddc:004 open_access

New Fault Tolerant Subset Preservers Bodwin, Greg Choudhary, Keerti Parter, Merav Shahar, Noa Subset Preservers Distances Fault-tolerance 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.) Schloss Dagstuhl – Leibniz-Zentrum für Informatik Greg Bodwin and Keerti Choudhary and Merav Parter and Noa Shahar 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.15 urn:nbn:de:0030-drops-124222 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.15 eng https://creativecommons.org/licenses/by/3.0/legalcode