License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2022.32
URN: urn:nbn:de:0030-drops-172239
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17223/
Parter, Merav ;
Petruschka, Asaf
Õptimal Dual Vertex Failure Connectivity Labels
Abstract
In this paper we present succinct labeling schemes for supporting connectivity queries under vertex faults. For a given n-vertex graph G, an f-VFT (resp., EFT) connectivity labeling scheme is a distributed data structure that assigns each of the graph edges and vertices a short label, such that given the labels of a vertex pair u and v, and the labels of at most f failing vertices (resp., edges) F, one can determine if u and v are connected in G ⧵ F. The primary complexity measure is the length of the individual labels. Since their introduction by [Courcelle, Twigg, STACS '07], FT labeling schemes have been devised only for a limited collection of graph families. A recent work [Dory and Parter, PODC 2021] provided EFT labeling schemes for general graphs under edge failures, leaving the vertex failure case fairly open.
We provide the first sublinear f-VFT labeling schemes for f ≥ 2 for any n-vertex graph. Our key result is 2-VFT connectivity labels with O(log³ n) bits. Our constructions are based on analyzing the structure of dual failure replacement paths on top of the well-known heavy-light tree decomposition technique of [Sleator and Tarjan, STOC 1981]. We also provide f-VFT labels with sub-linear length (in |V|) for any f = o(log log n), that are based on a reduction to the existing EFT labels.
BibTeX - Entry
@InProceedings{parter_et_al:LIPIcs.DISC.2022.32,
author = {Parter, Merav and Petruschka, Asaf},
title = {{\~{O}ptimal Dual Vertex Failure Connectivity Labels}},
booktitle = {36th International Symposium on Distributed Computing (DISC 2022)},
pages = {32:1--32:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-255-6},
ISSN = {1868-8969},
year = {2022},
volume = {246},
editor = {Scheideler, Christian},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17223},
URN = {urn:nbn:de:0030-drops-172239},
doi = {10.4230/LIPIcs.DISC.2022.32},
annote = {Keywords: Fault-Tolerance, Heavy-Light Decomposition, Labeling Schemes}
}
Keywords: |
|
Fault-Tolerance, Heavy-Light Decomposition, Labeling Schemes |
Collection: |
|
36th International Symposium on Distributed Computing (DISC 2022) |
Issue Date: |
|
2022 |
Date of publication: |
|
17.10.2022 |