2026-07-26T03:03:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17223 2024-03-06T10:59:16Z ddc:004 open_access

Õptimal Dual Vertex Failure Connectivity Labels Parter, Merav Petruschka, Asaf Fault-Tolerance Heavy-Light Decomposition Labeling Schemes 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Merav Parter and Asaf Petruschka 2022 Is Part Of LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2022.32 urn:nbn:de:0030-drops-172239 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.32 eng https://creativecommons.org/licenses/by/4.0/legalcode