2024/02/19 by Petruschka, Asaf, Sapir, Shay, Tzalik, Elad
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2402.12144
Fault-tolerant connectivity labelings are schemes that, given an n-vertex graph G=(V,E) and f≥ 1, 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 |F|≤ f, one can determine if u,v are connected in G-F, the surviving graph after removing F. For the edge or vertex faults models, i.e., F⊆ E or F⊆ V, a sequence of recent work established schemes with poly(f,log n)-bit labels. 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. Our main contribution is settling the label length complexity for connectivity under one color fault (f=1). The existing implicit solution, by applying the state-of-the-art scheme for edge faults of [Dory and Parter, PODC'21], might yield labels of Ω(n) bits. We provide a deterministic scheme with labels of 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 cannot produce asymptotically smaller labels. We extend our labeling approach to yield a routing scheme avoiding a single forbidden color. We also consider the centralized setting, and show an O(n)-space oracle, answering connectivity queries under one color fault in O(1) time. Turning to f≥ 2 color faults, we give a randomized labeling scheme with O(n1-1/2f)-bit labels, along with a lower bound of Ω(n1-1/(f+1)) bits.