Bodwin, Greg ;
Choudhary, Keerti ;
Parter, Merav ;
Shahar, Noa
New Fault Tolerant Subset Preservers
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 nontrivial 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 nvertex undirected weighted graph or weighted DAG G = (V,E) and S ⊆ V, we present a construction of a subset preserver with Õ(Sn) 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 nearlymatching lower bound of Ω(Sn) in either setting, and we show that the same lower bound holds conditionally even if attention is restricted to unweighted graphs.
 For an nvertex 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 nvertex 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.)
BibTeX  Entry
@InProceedings{bodwin_et_al:LIPIcs:2020:12422,
author = {Greg Bodwin and Keerti Choudhary and Merav Parter and Noa Shahar},
title = {{New Fault Tolerant Subset Preservers}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {15:115:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771382},
ISSN = {18688969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12422},
URN = {urn:nbn:de:0030drops124222},
doi = {10.4230/LIPIcs.ICALP.2020.15},
annote = {Keywords: Subset Preservers, Distances, Faulttolerance}
}
29.06.2020
Keywords: 

Subset Preservers, Distances, Faulttolerance 
Seminar: 

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Issue date: 

2020 
Date of publication: 

29.06.2020 