Connectivity Labeling in Faulty Colored Graphs

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 Õ(√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 Õ(n)-space oracle, answering connectivity queries under one color fault in Õ(1) time. Turning to f≥ 2 color faults, we give a randomized labeling scheme with Õ(n1-1/2ᶠ)-bit labels, along with a lower bound of Ω(n1-1/(f+1)) bits.