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, 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 (n^1-1/2ᶠ) -bit labels, along with a lower bound of (n^1-1/ (f+1) ) bits.