Connectivity Labeling in Faulty Colored Graphs
Distributed Computing · 2026-06 · 39 (2)
DOI: 10.1007/s00446-026-00506-1 ↗Kurz gefasst
Fachartikel in der Zeitschrift Distributed Computing, online erschienen am 07.04.2026. Verfasst von Asaf Petruschka und 2 weiteren Autor:innen. Beteiligte Einrichtung: Weizmann Institute, Rehovot, Israel. Die Arbeit nennt 49 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: HORIZON EUROPE European Research Council, Azrieli Foundation, Israeli Council for Higher Education.
Abstract (Originalsprache)
Fault-tolerant connectivity labelings are schemes that, given an n -vertex graph $$G=(V,E)$$ G = ( V , E ) and a parameter f , produce succinct yet informative labels for the elements of the graph. Given only the labels of two vertices u , v and of the elements in a faulty-set F with $$\vert F\vert \le f$$ | F | ≤ f , one can determine if u , v are connected in $$G-F$$ G - F , the surviving graph after removing F . For the edge or vertex faults models, i.e., $$F\subseteq E$$ F ⊆ E or $$F \subseteq V$$ F ⊆ V , a sequence of recent work established schemes with $$\operatorname {poly}(f,\log n)$$ poly ( f , log n ) -bit labels for general graphs. This paper considers the color faults model, recently introduced in the context of spanners [Petruschka, Sapir and Tzalik, ITCS ’24], which accounts for known correlations between failures. Here, the edges (or vertices) of the input G are arbitrarily colored, and the faulty elements in F are colors; a failing color causes all edges (vertices) of that color to crash. While treating color faults by naïvly applying solutions for many failing edges or vertices is inefficient, the known correlations could potentially be exploited to provide better solutions. Our main contribution is settling the label length complexity for connectivity under one color fault ( $$f=1$$ f = 1 ). The existing implicit solution, by black-box application of the state-of-the-art scheme for edge faults of [Dory and Parter, PODC ’21], might yield labels of $$\Omega (n)$$ Ω ( n ) bits. We provide a deterministic scheme with labels of $$\tilde{O}(\sqrt{n})$$ O ~ ( n ) bits in the worst case, and a matching lower bound. Moreover, our scheme is universally optimal : even schemes tailored to handle only colorings of one specific graph topology (i.e., may store the topology “for free”) cannot produce asymptotically smaller labels. We characterize the optimal length by a new graph parameter $$\textsf{bp}(G)$$ bp ( G ) called the ball packing number . We further extend our labeling approach to yield a routing scheme avoiding a single forbidden color, with routing tables of size $$\tilde{O}(\textsf{bp}(G))$$ O ~ ( bp ( G ) ) bits. We also consider the centralized setting, and show an $$\tilde{O}(n)$$ O ~ ( n ) -space oracle, answering connectivity queries under one color fault in $$\tilde{O}(1)$$ O ~ ( 1 ) time. Curiously, by our results, no oracle with such space can be evenly distributed as labels. Turning to $$f\ge 2$$ f ≥ 2 color faults, we give a randomized labeling scheme with $$\tilde{O}(n^{1-1/2^f})$$ O ~ ( n 1 - 1 / 2 f ) -bit labels, along with a lower bound of $$\Omega (n^{1-1/(f+1)})$$ Ω ( n 1 - 1 / ( f + 1 ) ) bits. For $$f=2$$ f = 2 , we make partial improvement by providing labels of $$\tilde{O}(\textrm{diam}(G)\sqrt{n})$$ O ~ ( diam ( G ) n ) bits, and show that this scheme is (nearly) optimal when $$\textrm{diam}(G)=\tilde{O}(1)$$ diam ( G ) = O ~ ( 1 ) . Additionally, we present a general reduction from the above all-pairs formulation of fault-tolerant connectivity labeling (in any fault model) to the single-source variant, which could also be applicable for centralized oracles, streaming, or dynamic algorithms.
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- Weizmann Institute, Rehovot, Israel.
Förderung
- HORIZON EUROPE European Research Council
- Azrieli Foundation
- Israeli Council for Higher Education
- Israel Academy of Sciences and Humanities
Zitieren
APA
Petruschka, A., Sapir, S., & Tzalik, E. (2026). Connectivity Labeling in Faulty Colored Graphs. Distributed Computing, 39(2). https://doi.org/10.1007/s00446-026-00506-1
Vancouver
Petruschka A, Sapir S, Tzalik E. Connectivity Labeling in Faulty Colored Graphs. Distributed Computing. 2026;39(2). doi:10.1007/s00446-026-00506-1
BibTeX
@article{Petruschka2026,
author = {Petruschka, Asaf and Sapir, Shay and Tzalik, Elad},
title = {Connectivity Labeling in Faulty Colored Graphs},
journal = {Distributed Computing},
year = {2026},
volume = {39},
number = {2},
doi = {10.1007/s00446-026-00506-1}
}
EUVIMED