# Connectivity Labeling in Faulty Colored Graphs

Asaf Petruschka Shay Sapir Elad Tzalik
Weizmann Institute of Science
<EMAIL_ADDRESS>Supported by the
European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme, grant agreement No. 949083, and by the
Israeli Science Foundation (ISF), grant 2084/18.This research was partially
supported by the Israeli Council for Higher Education (CHE) via the Weizmann
Data Science Research Center.

###### Abstract

Fault-tolerant connectivity labelings are schemes that, given an $n$-vertex
graph $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 $|F|\leq 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\subseteq E$ or $F\subseteq V$, a
sequence of recent work established schemes with $\operatorname{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$). 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)$ bits. We provide a
deterministic scheme with labels of $\tilde{O}(\sqrt{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 $\mathsf{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}(\mathsf{bp}(G))$ bits.
We also consider the _centralized_ setting, and show an $\tilde{O}(n)$-space
oracle, answering connectivity queries under one color fault in $\tilde{O}(1)$
time. Curiously, by our results, no oracle with such space can be _evenly_
distributed as labels.

Turning to $f\geq 2$ color faults, we give a randomized labeling scheme with
$\tilde{O}(n^{1-1/2^{f}})$-bit labels, along with a lower bound of
$\Omega(n^{1-1/(f+1)})$ bits. For $f=2$, we make partial improvement by
providing labels of $\tilde{O}(\mathrm{diam}(G)\sqrt{n})$ bits, and show that
this scheme is (nearly) optimal when $\mathrm{diam}(G)=\tilde{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.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Results
      1. 1.1.1 Single Color Fault ($f=1$)
      2. 1.1.2 $f$ Color Faults
      3. 1.1.3 Two Color Faults and Graphs of Bounded Diameter
      4. 1.1.4 Equivalence Between All-Pairs and Single-Source Connectivity
  2. 2 Preliminaries
  3. 3 Single Color Fault
    1. 3.1 Our Scheme and the Ball Packing Number
    2. 3.2 A Ball-Packing Lower Bound
    3. 3.3 Centralized Oracles and Nearest Colored Ancestors
  4. 4 $f$ Color Faults
    1. 4.1 Upper Bound
      1. 4.1.1 Labeling Scheme for $f=o(\log\log n)$
      2. 4.1.2 Labeling Scheme for $f=\Omega(\log\log n)$
    2. 4.2 Lower Bound
  5. 5 Two Color Faults in Small-Diameter Graphs
    1. 5.1 Upper Bound
    2. 5.2 Lower Bounds
  6. 6 Conclusion
  7. A Reduction from All-Pairs to Single-Source
  8. B Routing
    1. B.1 Basic Tools
    2. B.2 High Level Overview of the Routing Scheme
    3. B.3 Construction of Routing Tables and Labels
    4. B.4 The Routing Procedure
  9. C Single Color Fault: Proof of Theorem 3.5
  10. D Nearest Colored Ancestor Labels
  11. E Limitations of the Lower Bound Technique of Theorem 4.6
  12. F Hitting Set

##  1 Introduction

Labeling schemes are important distributed graph data structures with diverse
applications in graph algorithms and distributed computing, concerned with
assigning the vertices of a graph (and possibly also other elements, such as
edges) with succinct yet informative _labels_. Many real-life networks are
often error-prone by nature, which motivates the study of fault-tolerant graph
structures and services. In a fault-tolerant connectivity labeling scheme, we
are given an $n$-vertex graph $G=(V,E)$ and an integer $f$, and should assign
short labels to the elements of $G$, such that the following holds: For every
pair of vertices $u,v\in V$ and faulty-set $F$ with $|F|\leq f$, one can
determine if $u$ and $v$ are connected in $G-F$ by merely inspecting the
labels of the elements in $\\{u,v\\}\cup F$. The main complexity measure is
the maximal _label length_ (in bits), while construction and query time are
secondary measures.

The concept of edge/vertex-fault-tolerant labeling, aka _forbidden set_
labeling, was explicitly introduced by Courcelle and Twigg [CT07]. Earlier
work on fault-tolerant connectivity and distance labeling focused on graph
families such as planar graphs and graphs with bounded treewidth or doubling
dimension [CT07, CGKT08, ACG12, ACGP16]. Up until recently, designing edge- or
vertex-fault-tolerant connectivity labels for general graphs remained fairly
open. Dory and Parter [DP21] were the first to construct _randomized_ labeling
schemes for connectivity under $f$ _edge_ faults, where a query is answered
correctly with high probability,111 Throughout, the term with high probability
(w.h.p.) stands for probability at least $1-1/n^{\alpha}$, where $\alpha>0$ is
a constant that can be made arbitrarily large through increasing the relevant
complexity measure by a constant factor.  with length of $O(\min\\{f+\log
n,\log^{3}n\\})$ bits. Izumi, Emek, Wadayama and Masuzawa [IEWM23]
derandomized this construction, showing _deterministic_ labels of
$\tilde{O}(f^{2})$ bits.222 Throughout, the $\tilde{O}(\cdot)$ notations hides
$\operatorname{polylog}(fn)$ factors.  Turning to $f$ _vertex_ faults, Parter
and Petruschka [PP22] designed connectivity labels for $f\leq 2$ with
$\tilde{O}(1)$ bits. Very recently, Parter, Petruschka and Pettie [PPP23]
provided a randomized scheme for $f$ vertex faults with $\tilde{O}(f^{3})$
bits and a derandomized version with $\tilde{O}(f^{7})$ bits, along with a
lower bound of $\Omega(f)$ bits.

In this work, we consider labeling schemes for connectivity under _color
faults_ , a model that was very recently introduced in the context of graph
spanners [PST24], which intuitively accounts for known correlations between
failures. In this model, the edges or vertices of the input graph $G$ are
arbitrarily partitioned into classes, or equivalently, associated with
_colors_ , and a set $F$ of $f$ such color classes might fail. A failing color
causes all edges (vertices) of that color to crash. The survivable subgraph
$G-F$ is formed by deleting every edge333In the edge-colored case, it is
natural to consider multi-graphs, where parallel edges may have different
colors. or vertex with color from $F$. The scheme must assign labels to the
vertices _and to the colors_ of $G$, so that a connectivity query
$\left<u,v,F\right>$ can be answered by inspecting only the labels of the
vertices $u,v$ and of the colors in $F$.

This new notion generalizes edge/vertex fault-tolerant schemes, that are
obtained in the special case when each edge or vertex has a unique color.
However, in the general case, even a single color fault may correspond to many
and arbitrarily spread edge/vertex faults, which poses a major challenge.
Tackling this issue by naively applying the existing solutions for many
individual edge/vertex faults (i.e., by letting the label of a color store all
labels given to elements in its class) may result in very large labels of
$\Omega(n)$ bits or more, even when $f=1$. On a high level, this work shows
that the correlation between the faulty edges/vertices, predetermined by the
colors, can be used to construct much better solutions.

##### Related Work on Colored Graphs.

Faulty colored classes have been used to model Shared Risk Resource Groups
(SRRG) in optical telecommunication networks, multi-layered networks, and
various other practical contexts; see [CDP+07, Kui12, ZCTZ11] and the
references therein. Previous work mainly focused on centralized algorithms for
colored variants of classical graph problems (and their hardness). A notable
such problem is diverse routing, where the goal is to find two (or more) color
disjoint paths between two vertices [Hu03, EBR+03, MN02]. Another is the
colored variant of minimum cut, known also as the _hedge connectivity_ , where
the objective is to determine the minimum number of colors (aka hedges) whose
removal disconnects the graph; see e.g. [GKP17, XS20, FPZ23].

A different line of work focuses on distances to or between color classes, and
specifically on (centralized) data structures that, given a query
$\left<v,c\right>$, report the closest $c$-colored vertex to $v$ in the graph,
or the (approximate) distance from it [HLWY11, Che12, LM19, GLMW18, Tsu18,
EFW21].

###  1.1 Our Results

We initiate the study of fault-tolerant labeling schemes in colored graphs.
All of our results apply both to edge-colored and to vertex-colored
(multi)-graphs.

####  1.1.1 Single Color Fault ($f=1$)

For $f=1$, i.e., a single faulty color, we (nearly) settle the complexity of
the problem, by showing a simple construction of labels with length
$O(\sqrt{n}\log n)$ bits, along with a matching lower bound of
$\Omega(\sqrt{n})$ bits. In fact, our scheme provides a strong beyond worst-
case guarantee: for every given graph $G$, the length of the assigned labels
is (nearly) the best possible, even compared to schemes that are tailor-made
to only handle colorings of the topology in $G$,444 By the _topology_ of $G$,
we mean the uncolored graph obtained from $G$ by ignoring the colors. Slightly
abusing notation, we refer to this object as _the graph topology_ $G$, rather
than the (colored) graph $G$.  or equivalently, are allowed to store the
uncolored topology “for free” in all the labels. Guarantees of this form,
known as _universal optimality_ , have sparked major interest in the graph
algorithms community, and particularly in recent years, following the
influential work of Haeupler, Wajc and Zuzic [HWZ21] in the distributed
setting.555One cannot compete with a scheme that is optimal for the given
graph _and_ its coloring (aka “instance optimal”), as such a tailor-made
scheme may store the entire colored graph “for free”, and the labels merely
need to specify the query. On an intuitive level, the universal optimality
implies that even when restricting attention to any class of graphs, e.g.
planar graphs, our scheme performs asymptotically as well as the optimal
scheme for this specific class.

Our universally optimal labels are based on a new graph parameter called the
_ball packing number_ , denoted by $\mathsf{bp}(G)$. Disregarding minor
nuances, $\mathsf{bp}(G)$ is the maximum integer $r$ such that one can fit $r$
disjoint balls of radius $r$ in the topology of $G$ (see formal definition in
Section 3.1). The ball packing number of an $n$-vertex graph is always at most
$\sqrt{n}$, but often much smaller. For example, $\mathsf{bp}(G)$ is smaller
than the _diameter_ of $G$. In Section 3, we show the following:

######  Theorem 1.1 ($f=1$, informal).

There is a connectivity labeling scheme for one color fault, that for every
$n$-vertex graph $G$, assigns $O(\mathsf{bp}(G)\log n)$-bit labels. Moreover,
$\Omega(\mathsf{bp}(G))$-bit labels are necessary, even for labeling schemes
tailor-made for the topology of $G$, i.e., where the uncolored topology is
given in addition to the query labels.

The lower bound in Theorem 1.1 is information-theoretic, obtained via
communication complexity. On a high level, we argue that one can encode
$\mathsf{bp}(G)^{2}$ arbitrary bits by taking the following two steps: (1)
coloring the balls that certify the ball packing number using $\mathsf{bp}(G)$
many colors, and (2) storing the labels of those colors and of additional
$O(\mathsf{bp}(G))$ vertices. The upper bound is based on observing that (when
$G$ is connected) there is a subset $A$ of $O(\mathsf{bp}(G))$ vertices which
is _$O(\mathsf{bp}(G))$ -ruling_: every vertex in $G$ has a path to $A$ of
length $O(\mathsf{bp}(G))$. Intuitively, this enables the label of a color $c$
to store the identifiers of the connected components of each $a\in A$ in
$G-c$, while the label of a vertex $v$ only stores the identifiers of the
connected components of $v$ with respect to faults of colors on its path to
$A$.

Additionally, we consider the closely related problem of _routing_ messages
over $G$ while avoiding any one forbidden color. We extend our labeling
approach, and show:

######  Theorem 1.2 (Forbidden color routing, informal).

There is a routing scheme for avoiding one forbidden color in a colored
$n$-vertex graph $G$, with routing tables and labels of size
$O(\mathsf{bp}(G)\log n)$ bits, and message header of size $O(\log n)$ bits.

See Appendix B for formal definitions, and a detailed discussion of our
routing scheme. We note that our routing scheme does not provide good distance
(aka stretch) guarantees for the routing path, and optimizing it is an
interesting direction for future work.

We end our discussion for $f=1$ by considering _centralized oracles_ (data
structures) for connectivity under a single color fault. In this setting, one
can utilize centralization to improve on the naive approach of storing all
labels. We note that this problem can be solved using existing $O(n)$-space
and $O(\log\log n)$-query time oracles for _nearest colored ancestor_ on trees
[MM96, GLMW18], yielding the same bounds for single color fault connectivity
oracles. Interestingly, our lower bound shows that oracles with such space
cannot be evenly distributed into labels. We are unaware of similar ‘gap’
phenomena between the distributed and centralized variants of graph data
structures.

####  1.1.2 $f$ Color Faults

It has been widely noted that in fault-tolerant settings, handling even two
faults may be significantly more challenging than handling a single fault.
Such phenomena appeared, e.g., in distance oracles [DP09], min-cut oracles
[BBP22], reachability oracles [Cho16] and distance preservers [Par15, GK17,
Par20]. In our case, this is manifested in generalized upper and lower bounds
on the label length required to support $f$ color faults, exhibiting a gap
when $f\geq 2$; our upper bound is roughly $\tilde{O}(n^{1-1/2^{f}})$ bits,
while the lower bound is $\Omega(n^{1-1/(f+1)})$ bits (both equal
$\tilde{\Theta}(\sqrt{n})$ when $f=1$).

######  Theorem 1.3 ($f\geq 2$ upper bound, informal).

There is a randomized labeling scheme for connectivity under $f$ color faults
with label length of
$\min\\{fn^{1-1/2^{f}},n\\}\cdot\operatorname{polylog}(fn)$ bits.

######  Theorem 1.4 ($f\geq 2$ lower bound, informal).

A labeling scheme for connectivity under $f$ color faults must have label
length of $\Omega(n^{1-1/(f+1)})$ bits for constant $f$, hence
$\Omega(n^{1-o(1)})$ bits for $f=\omega(1)$.

The full discussion appears in Section 4. Apart from the gap between the
bounds, there are a few more noteworthy differences from the case of a single
color fault.

First, the scheme of Theorem 1.3 is _randomized_ , as opposed to the
deterministic scheme for $f=1$ (Theorem 1.1). Moreover, the construction is
based on different techniques, combining three main ingredients: (1)
sparsification tools for colored graphs [PST24], (2) the (randomized) edge
fault-tolerant labeling scheme of [DP21], and (3) a recursive approach of
[PP22].

Second, the lower bound of Theorem 1.4 is _existential_ (but still
information-theoretic): it relies on choosing a fixed ‘worst-case’ graph
topology, and encoding information by coloring it and storing some of the
resulting labels. We further argue that this technique cannot yield a lower
bound stronger than $\tilde{\Omega}(n^{1-1/(f+1)})$ bits. This is due to the
observation that a color whose label is not stored can be considered _never
faulty_ , combined with the existence of efficient labeling schemes when the
number of colors is small. A detailed discussion of this barrier appears in
Section 4.2.

Curiously, in the seemingly unrelated problem of small-size fault-tolerant
distance preserves (FT-BFS) introduced by Parter and Peleg [PP13], there is a
similar gap in the known bounds for $f\geq 3$, of $O(n^{2-1/2^{f}})$ and
$\Omega(n^{2-1/(f+1)})$ edges [Par15, BGPW17]. Notably, for the case of $f=2$,
Parter [Par15] provided a tight upper bound of $O(n^{5/3})$, later simplified
by Gupta and Khan [GK17]. Revealing connections between FT-BFS structures and
the labels problem of this paper is an intriguing direction for future work.

####  1.1.3 Two Color Faults and Graphs of Bounded Diameter

For the special case of two color faults, we provide another scheme, with
label length of $\tilde{O}(D\sqrt{n})$ bits for graphs of diameter at most
$D$.

######  Theorem 1.5 ($f=2$ upper bound, informal).

There is a labeling scheme for connectivity under two color faults with label
length of $\tilde{O}(D\sqrt{n})$ bits.

This beats the general scheme when $D=O(n^{1/4-\epsilon})$, and demonstrates
that the existential $\Omega(n^{2/3})$ lower bound does not apply to graphs
with diameter $D=O(n^{1/6-\epsilon})$. Further, this scheme is existentially
optimal (up to logarithmic factors) for graphs with $D=\tilde{O}(1)$. We hope
this construction, found in Section 5, could serve as a stepping stone towards
closing the current gap between our bounds, and towards generalizing
$\mathsf{bp}(G)$ for the case of $f=2$.

Table 1 summarizes our main results on connectivity labeling under color
faults.

Table 1: A summary of our results on $f$ color fault-tolerant connectivity labeling schemes. The table shows the provided length bounds (in bits) for such schemes. No. faults | Upper bound | Lower bound
---|---|---
$f=1$ | $\tilde{O}(\sqrt{n})$ | Thm 3.5 | $\Omega(\sqrt{n})$ | Thm 3.6
$f=2$ | $\tilde{O}(\operatorname{diam}(G)\sqrt{n})$ | Thm 5.1 | $\Omega(n^{2/3})$ | Thm 4.6
$\tilde{O}(n^{3/4})$ | Thm 4.1
$f=O(1)$ | $\tilde{O}(n^{1-1/2^{f}})$ | $\Omega(n^{1-1/(f+1)})$
$f=\omega(1)$ | $\tilde{O}(n)$ | $\Omega(n^{1-o(1)})$

####  1.1.4 Equivalence Between All-Pairs and Single-Source Connectivity

In the _single-source_ variant of fault-tolerant connectivity, given are an
$n$-vertex graph $G$ with a designated _source vertex_ $s$, and an integer
$f$. It is then required to support queries of the form $\left<u,F\right>$,
where $u\in V$ and $F$ is a faulty-set of size at most $f$, by reporting
whether $u$ is connected to $s$ in $G-F$. Here, and throughout this
discussion, we do not care about the type of faulty elements; these could be
edges, vertices or colors. For concreteness, we focus our discussion on
labeling schemes, although it applies more generally to other models, e.g.,
centralized oracles, streaming, and dynamic algorithms. Clearly, every
labeling scheme for _all-pairs_ fault-tolerant connectivity can be transformed
into a single-source variant by including $s$’s label in all other labels,
which at most doubles the label length. We consider the converse direction,
and show that a single-source scheme can be used as a black-box to obtain an
all-pairs scheme with only a small overhead in length.

######  Theorem 1.6 (Single-source reduction, informal).

Suppose there is a single-source $f$ fault-tolerant connectivity labeling
scheme using labels of at most $b(n,f)$ bits. Then, there is an all-pairs $f$
fault-tolerant connectivity labeling scheme with $\tilde{O}(b(n+1,f))$-bit
labels.

The reduction is based on the following idea. Suppose we add a new source
vertex $s$ to $G$, and include each edge from $s$ to the other vertices
independently with probability $p$. Given a query $\left<u,v,F\right>$, if
$u,v$ are originally connected in $G-F$, they must agree on connectivity to
the new source $s$, regardless of $p$. However, if $u,v$ are disconnected in
$G-F$, and $p$ is such that $1/p$ is roughly the size of $u$’s connected
component in $G-F$, then with constant probability, $u$ and $v$ will disagree
on connectivity to $s$. The full proof appears in Appendix A.

##  2 Preliminaries

##### Colored Graphs.

Throughout, we denote the given input graph by $G$, which is an undirected
graph with $n$ vertices $V=V(G)$, and $m$ edges $E=E(G)$. The graph $G$ may be
a multi-graph, i.e., there may be several different edges with the same
endpoints (parallel edges). The edges or the vertices of $G$ are each given a
color from a set of $C$ possible colors. The coloring is _arbitrary_ ; there
are no ‘legality’ restrictions (e.g., edges sharing an endpoint may have the
same color). Without loss of generality, we sometimes assume that
$C\leq\max\\{m,n\\}$, and that the set of colors is $[C]$. For a (faulty)
subset of colors $F$, we denote by $G-F$ the subgraph of $G$ where all edges
(or vertices) with color from $F$ are deleted. When $F$ is a singleton
$F=\\{c\\}$, we use the shorthand $G-c$.

In some cases, we refer only to the _topology_ of the graph, and ignore the
coloring. Put differently, we sometimes consider the family of inputs given by
all different colorings of a fixed graph. This object is referred to as the
graph _topology_ $G$, rather than the graph $G$. We denote by
$\operatorname{dist}_{G}(u,v)$ the number of edges in a $u$-$v$ shortest path
(and $\infty$ if no such path exist). For a non-empty $A\subseteq V$, the
distance from $u\in V$ to $A$ is defined as
$\operatorname{dist}_{G}(u,A)=\min\\{\operatorname{dist}_{G}(u,a)\mid a\in
A\\}$.

Our presentation focuses, somewhat arbitrarily, on the _edge-colored_ case;
throughout, this case is assumed to hold unless we explicitly state otherwise.
This is justified by the following discussion.

##### Vertex vs. Edge Colorings.

An edge-colored instance can be reduced to a vertex-colored one, and vice
versa, by subdividing each edge666Throughout, we slightly abuse notation and
write $e=\\{u,v\\}$ to say that $e$ has endpoints $u,v$, even though there
might be several different edges with these endpoints. $e=\\{u,v\\}$ into two
edges $\\{u,x_{e}\\}$ and $\\{x_{e},v\\}$, where $x_{e}$ is a new vertex. If
the original instance has edge colors, we give the new instance vertex colors,
by coloring each new vertex $x_{e}$ with the original color of the edge $e$.
(The original vertices get a new ‘never-failing’ color.) For the other
direction, we color each of $\\{u,x_{e}\\}$ and $\\{x_{e},v\\}$ by the color
of the original vertex incident to it, i.e., $\\{u,x_{e}\\}$ gets $u$’s color,
and $\\{x_{e},v\\}$ gets $v$’s color.

These easy reductions increase the number of vertices to $n+m$, which a prioi
might seem problematic. However, as shown by [PST24], given any fixed
(constant) bound $f$ on the number of faulty colors, one can replace a given
input instance (either vertex- or edge-colored) by an equivalent sparse
subgraph with only $\tilde{O}(n)$ edges, that has the same connectivity as the
original graph under any set of at most $f$ color faults. So, by sparsifying
before applying the reduction, the number of vertices increases only to
$\tilde{O}(n)$. Moreover, all our results translate rather seamlessly between
the edge-colored and the vertex-colored cases, even without the general
reductions presented above.

##### Vertex and Component IDs.

We assume w.l.o.g. that the vertices have unique $O(\log n)$-bit identifiers
from $[n]$, where $\mathsf{id}(v)$ denotes the identifier of $v\in V$. Using
these, we define identifiers for connected components in subgraphs of $G$, as
follows. When $G^{\prime}$ is a subgraph of $G$ and $v\in V(G^{\prime})$, we
define $\mathsf{cid}(v,G^{\prime})=\min\\{\mathsf{id}(u)\mid\text{$u,v$
connected in $G^{\prime}$}\\}$. This ensures
$\mathsf{cid}(u,G^{\prime})=\mathsf{cid}(v,G^{\prime})$ iff $u,v$ are in the
same connected component in $G^{\prime}$. Therefore, if one can compute
$\mathsf{cid}(v,G-F)$ from the labels of $v,F$, then, using the same labels,
one can answer connectivity queries subject to faults.

##### Indexing Lower Bound.

Our lower bounds rely on the classic _indexing_ lower bound from communication
complexity. In the one-way communication problem $\textsc{Index}(N)$, Alice
holds a string $x\in\\{0,1\\}^{N}$, and Bob holds an index $i\in[0,N-1]$. The
goal is for Alice to send a message to Bob, such that Bob can recover $x_{i}$,
the $i$-th bit of $x$. Crucially, the communication is one-way; Bob cannot
send any message to Alice. The protocols are allowed to be randomized, in
which case both Alice and Bob have access to a public random string. The
following lower bound on the number of bits Alice is required to send is well-
known (see [KN96, KNR99, JKS08]).

######  Lemma 2.1 (Indexing Lower Bound [KNR99]).

Every one-way communication protocol (even with shared randomness) for
$\textsc{Index}(N)$ must use $\Omega(N)$ bits of communication.

##  3 Single Color Fault

In this section, we study the connectivity problem under one color fault. That
is, given two vertices $u,v$ and a faulty color $c$, one should be able to
determine if $u,v$ are connected in $G-c$. In Sections 3.1 and 3.2 we focus on
labeling schemes, and provide universally optimal upper and lower bounds. In
Section 3.3 we change gears and provide centralized oracles for this problem.

###  3.1 Our Scheme and the Ball Packing Number

We first show a scheme that works when $G$ is connected.777 Connectivity
cannot be assumed without losing generality, because of the color labels. A
color gets _only one_ label, which should support connectivity queries in
_every_ connected component of the input graph.  Later, we show how to remove
this assumption. Consider the following procedure: starting from an arbitrary
vertex $a_{0}$, iteratively choose a vertex $a_{i}$ which satisfies

$\operatorname{dist}_{G}(a_{i},\\{a_{0},\dots,a_{i-1}\\})=i,$

until no such vertex exists. Suppose the procedure halts at the $k$-th
iteration, with the set of chosen vertices $A=\\{a_{0},\dots,a_{k-1}\\}$. Then
every vertex $v\in V$ has distance less than $k$ from $A$. We use $A$ to
construct $O(k\log n)$-bit labels, as follows.

  * •

Label $L(c)$ of color $c\in[C]$: For every $a\in A$, store
$\mathsf{cid}(a,G-c)$.

  * •

Label $L(v)$ of vertex $v\in V$: Let $P(v)$ be a shortest path connecting $v$
to $A$, and let $a(v)$ be its endpoint in $A$. For every color $c$ present in
$P(v)$, store $\mathsf{cid}(v,G-c)$. Also, store $\mathsf{id}(a(v))$.

Answering queries is straightforward as given $L(v)$ and $L(c)$, one can
readily compute $\mathsf{cid}(v,G-c)$: If the color $c$ appears on the path
$P(v)$, then $\mathsf{cid}(v,G-c)$ is found in $L(v)$. Otherwise, $P(v)$
connects between $v$ and $a(v)$ in $G-c$, hence
$\mathsf{cid}(v,G-c)=\mathsf{cid}(a(v),G-c)$, and the latter is stored in
$L(c)$.

The labels have length of $O(\sqrt{n}\log n)$ bits, as follows. Consider the
$A$-vertices chosen at iteration $\lceil k/2\rceil$ or later. By construction,
each of these $\lfloor k/2\rfloor$ vertices is at distance at least $\lceil
k/2\rceil$ from all others. Hence, the balls of radius $\lfloor k/4\rfloor$
(in the metric induced by $G$) centered at these vertices are disjoint, and
each such ball contains at least $\lfloor k/4\rfloor$ vertices. Thus, $\lfloor
k/2\rfloor\cdot\lfloor k/4\rfloor\leq n$, so $k=O(\sqrt{n})$.

The length of the labels assigned by this simple scheme turns out to be not
only _existentially optimal_ , but also _universally optimal_ (both up to a
factor of $\log n$). By existential optimality, we mean that every labeling
scheme for connectivity under one color fault must have $\Omega(\sqrt{n})$-bit
labels on some _worst-case colored graph $G$_. The stronger universal
optimality means that for _every graph topology $G$_, every such labeling
scheme, even tailor-made for $G$, must assign $\Omega(k)$-bit labels (for some
coloring of $G$).

##### The Ball-Packing Number.

To prove the aforementioned universal optimality of our scheme, we introduce a
graph parameter called the _ball-packing number_. As the name suggests, this
parameter concerns packing disjoint balls in the metric induced by the graph
topology $G$. Its relation to faulty-color connectivity is hinted by the
previous analysis using a “ball packing argument” to obtain the
$\tilde{O}(\sqrt{n})$ bound. We next give the formal definitions and some
immediate observations.

######  Definition 3.1 (Proper $r$-ball).

For every integer $r\geq 0$, the _$r$ -ball_ in $G$ centered at $v\in V(G)$,
denoted $B_{G}(v,r)$, consists of all vertices of distance at most $r$ from
$v$. That is,

$B_{G}(v,r)\stackrel{{\scriptstyle\operatorname{def}}}{{=}}\\{u\in
V(G)\mid\operatorname{dist}_{G}(v,u)\leq r\\}.$

An $r$-ball is called _proper_ if there exists $u\in B_{G}(v,r)$ that realizes
the radius, i.e., $\operatorname{dist}_{G}(u,v)=r$.888 If the distance $r$
from $v$ is not realized, then there exists $r^{\prime}<r$ such that the
distance $r^{\prime}$ _is_ realized, and $B_{G}(v,r^{\prime})=B_{G}(v,r)$ _as
sets of vertices_. So, whether $B(v,r)$ is proper depends not only on the set
of vertices in this ball, but also on the specified parameter $r$.

######  Observation 3.2.

If $r\leq\operatorname{dist}_{G}(u,v)<\infty$, then $B_{G}(u,r)$ and
$B_{G}(v,r)$ are proper $r$-balls.

######  Definition 3.3 (Ball-packing number).

The _ball-packing number_ of $G$, denoted $\mathsf{bp}(G)$, is the maximum
integer $r$ such that there exist at least $r$ vertex-disjoint proper
$r$-balls in $G$.

######  Observation 3.4.

(i) For every $n$-vertex graph $G$, $\mathsf{bp}(G)\leq\sqrt{n}$. (ii) For
some graphs $G$, we also have $\mathsf{bp}(G)=\Omega(\sqrt{n})$ (e.g., when
$G$ is a path).

##### A Ball-Packing Upper Bound.

Our length analysis for the above scheme in fact showed the existence of at
least $\lfloor k/2\rfloor$ disjoint and proper $\lfloor k/4\rfloor$-balls,
implying that $k=O(\mathsf{bp}(G))$ by Definition 3.3. Minor adaptations to
this scheme to handle several connected components in $G$ yields the following
theorem, whose proof is deferred to Appendix C.

######  Theorem 3.5.

There is a deterministic labeling scheme for connectivity under one color
fault that, when given as input an $n$-vertex graph $G$, assigns labels of
length $O(\mathsf{bp}(G)\log n)$ bits. The query time is $O(1)$ (in the RAM
model).

######  Remark.

By 3.4(i), the label length is always bounded by $O(\sqrt{n}\log n)$ bits.

###  3.2 A Ball-Packing Lower Bound

We now show an $\Omega(\mathsf{bp}(G))$ bound on the maximal label length.

######  Theorem 3.6.

Let $G$ be a graph topology. Suppose there is a (possibly randomized) labeling
scheme for connectivity under one color fault, that assigns labels of length
at most $b$ bits for every coloring of $G$. Then $b=\Omega(\mathsf{bp}(G))$.

######  Remark.

By the above theorem and 3.4(ii), every labeling scheme for all topologies
must assign $\Omega(\sqrt{n})$-bit labels on some input, which proves Theorem
1.4 for the special case $f=1$.

###### Proof of Theorem 3.6.

Denote $r=\mathsf{bp}(G)$. The proof uses the labeling scheme and the graph
topology $G$ to construct a communication protocol for
$\textsc{Index}(r^{2})$. Let $x=x_{0}x_{1}\cdots x_{r^{2}-1}$ be the input
string given to Alice, where each $x_{i}\in\\{0,1\\}$. Let $i^{*}$ be the
index given to Bob, where $0\leq i^{*}\leq r^{2}-1$. On a high level, the
communication protocol works as follows. Both Alice and Bob know the
(uncolored) graph topology $G$ in advance, as part of the protocol. Alice
colors the edges of her copy of $G$ according to her input $x$, and applies
the labeling scheme to compute labels for the vertices and colors. She then
sends $O(r)$ such labels to Bob, and he recovers $x_{i^{*}}$ by using the
labels to answer a connectivity query in the colored graph. As the total
number of sent bits is $O(b\cdot r)$, it follows by Lemma 2.1 that $b\cdot
r=\Omega(r^{2})$, and hence $b=\Omega(r)=\Omega(\mathsf{bp}(G))$. The rest of
this proof is devoted to the full description of the protocol.

In order to color $G$, Alice does the following. She uses the color-palette
$\\{0,1,\dots,r-1\\}\cup\\{\perp\\}$, where the symbol $\perp$ is used instead
of $r$ to stress that $\perp$ is a special _never failing color_ in the
protocol. Let $v_{0},v_{1}\dots,v_{r-1}$ be centers of $r$ disjoint proper
$r$-balls in $G$, which exist by Definition 3.3 of Ball-Packing, and since
$r=\mathsf{bp}(G)$. For every $k,l\in[0,r)$, define

$E_{k,l}\stackrel{{\scriptstyle\operatorname{def}}}{{=}}\big{\\{}\\{u,w\\}\in
E\mid\text{$\operatorname{dist}_{G}(v_{k},u)=l$ and
$\operatorname{dist}_{G}(v_{k},w)=l+1$}\big{\\}}.$

In other words, $E_{k,l}$ is the set of edges connecting layers $l$ and $l+1$
of the $k$-th ball $B(v_{k},r)$. As the layers in a ball are disjoint, and the
balls themselves are disjoint, the sets $\\{E_{k,l}\\}_{k,l}$ are mutually
disjoint. Alice colors these edge-sets by the following rule: For every
$i\in[0,r^{2}-1]$, she decomposes it as $i=kr+l$ with $l,k\in[0,r)$. If
$x_{i}=1$, the edges in $E_{k,l}$ get the color $l$. Otherwise, when
$x_{i}=0$, these edges get the null-color $\perp$. Every additional edge in
$G$, outside of the sets $\\{E_{k,l}\\}_{k,l}$, is also colored by $\perp$.
The purpose of this coloring is to ensure the following property, for
$k,l\in[0,r)$ and $i=kr+l$: If $x_{i}=0$, then (the induced graph on)
$B_{G}(v_{k},r)$ does not contain any $l$-colored edges and its vertices are
connected in $G-l$. However, if $x_{i}=1$, then $E_{k,l}$ is colored by $l$,
hence in $G-l$, $v_{k}$ is disconnected from every $u$ for which
$\operatorname{dist}_{G}(u,v_{k})>l$.

Next, we describe the message sent by Alice. For $0\leq k\leq r-1$, let
$u_{k}\in V$ with $\operatorname{dist}_{G}(u_{k},v_{k})=r$, which exists by
Definition 3.1, as $B_{G}(v_{k},r)$ is a _proper_ $r$-ball. Alice applies the
labeling scheme on the colored $G$, and sends to Bob the labels of the
vertices $v_{0},\dots,v_{r-1},u_{0},\dots,u_{r-1}$, and of the colors
$0,\dots,r-1$. This amounts to $3r$ labels.

Finally, we describe Bob’s strategy. He decomposes $i^{*}$ as
$i^{*}=k^{*}r+l^{*}$ with $k^{*},l^{*}\in[0,r)$, and uses the labels of
$v_{k^{*}},u_{k^{*}},l^{*}$ to query the connectivity of $v_{k^{*}}$ and
$u_{k^{*}}$ in $G-l^{*}$. If the answer is _disconnected_ , Bob determines
that $x_{i^{*}}=1$, and if it is _connected_ , he determines that
$x_{i^{*}}=0$. By the previously described property of the coloring, Bob
indeed recovers $x_{i^{*}}$ correctly. Thus, this protocol solves
$\textsc{Index}(r^{2})$, which concludes the proof.

This proof extends quite easily to _vertex-colored_ graphs; Alice can color
the vertices in the $l$-th layer of $B(v_{k},r)$ instead of the edges
$E_{k,l}$. ∎

###  3.3 Centralized Oracles and Nearest Colored Ancestors

In the _centralized_ setting of oracles for connectivity under one color
fault, the objective is to preprocess the colored graph $G$ into a low-space
centralized data structure (oracle) that, when queried with (the
names/$\mathsf{id}$s of) two vertices $u,v\in V$ and a color $c$, can quickly
report if $u$ and $v$ are connected in $G-c$. The labeling scheme of Theorem
3.5 implies such a data structure with $O(n^{1.5})$ space and $O(1)$ query
time.999 The data structure stores all vertex labels, and the labels of all
colors that appear in some fixed maximal spanning forest $T$ of $G$. We can
ignore all other colors, as their failure does not change the connectivity in
$G$.  (The bounds for centralized data structures are in the standard RAM
model with $\Theta(\log n)$-bit words.) By the lower bound of Theorem 3.6,
such a data structure with space $o(n^{1.5})$ cannot be “evenly distributed”
into labels.

However, utilizing centralization, we can achieve $O(n)$ space with only
$O(\log\log n)$ query time. This is obtained by a reduction to the _nearest
colored ancestor_ problem, studied by Muthukrishnan and Müller [MM96] and by
Gawrychowski, Landau, Mozes and Weimann [GLMW18]. They showed that a rooted
$n$-vertex forest with colored vertices can be processed into an $O(n)$-space
data structure, that given a vertex $v$ and a color $c$, returns the nearest
$c$-colored ancestor of $v$ (or reports that none exist) in $O(\log\log n)$
time. The reduction is as follows. Choose a maximal spanning forest $T$ for
$G$, and root each tree of the forest in the vertex with minimum
$\mathsf{id}$. For each vertex $u\in V$, assign it with the color $d$ of the
edge connecting $u$ to its parent in $T$. Additionally, store
$\mathsf{cid}(u,G-d)$ in the vertex $u$. (The roots get a null-color and store
their $\mathsf{id}$s, which are also their $\mathsf{cid}$s in every subgraph
of $G$.) Now, construct a nearest color ancestor data structure for $T$ as in
[MM96, GLMW18]. Given a query $v\in V$ and color $c$, we can find the nearest
$c$-colored ancestor $w$ of $v$ in $O(\log\log n)$ time. As $w$ is nearest,
the $T$-path from $v$ to $w$ in $T$ does not contain $c$-colored edges,
implying that $\mathsf{cid}(v,G-c)=\mathsf{cid}(w,G-c)$, and the latter is
stored at $w$. (If no such $c$-colored ancestor exists, take $w$ as the root,
and proceed similarly.) Given $u,v\in V$ and color $c$, apply the above
procedure twice, and determine the connectivity of $u,v$ in $G-c$ by comparing
their $\mathsf{cid}$s, within $O(\log\log n)$ time. We therefore get:

######  Theorem 3.7.

Every colored $n$-vertex graph $G$ can be processed into an $O(n)$-space
centralized oracle that given a query of $u,v\in V$ and color $c$, reports if
$u,v$ are connected in $G-c$ in $O(\log\log n)$ time.

The reduction raises an alternative approach for constructing connectivity
labels for one color fault, via providing a labeling scheme for the nearest
colored ancestor problem. In Appendix D we show that indeed, such a scheme
with $\tilde{O}(\sqrt{n})$-bit labels exists.

##  4 $f$ Color Faults

In this section, we connectivity labeling under (at most) $f$ color faults,
for arbitrary $f$.

###  4.1 Upper Bound

We provide two labeling schemes for connectivity under $f$ color faults: the
first is better for small $f=o(\log\log n)$, and the second is good for larger
values of $f$. The following theorem is obtained by combining the two:

######  Theorem 4.1.

Let $f\geq 1$. There is a randomized labeling scheme for connectivity under
$\leq f$ color faults, assigning labels of length
$O(\min\\{fn^{1-1/2^{f}},n\\}\cdot\operatorname{polylog}(fn))$ bits on colored
$n$-vertex graphs.

We state two ingredients required by our scheme. The first is _color fault-
tolerant connectivity certificates_ , recently constructed by [PST24]. The
second is connectivity labels for _edge faults_ by Dory and Parter [DP21]:

######  Theorem 4.2 (Color fault-tolerant connectivity certificates [PST24,
Theorem 21]).

Given a colored $n$-vertex graph $G$, one can compute in polynomial time a
subgraph $H$ with $O(fn\log n)$ edges, that is an $f$-color fault-tolerant
connectivity certificate: for all $u,v\in V$ and sets $F$ of at most $f$
colors, $u,v$ are connected in $G-F$ iff they are connected in $H-F$.

######  Theorem 4.3 (Connectivity labels for edge faults [DP21, Theorem 3.7]).

There exists a randomized labeling scheme that, when given a multi-graph
$G=(V,E)$ with $n$ vertices and $m$ edges, assigns labels of $O(\log^{3}n+\log
m)$ bits to $V\cup E$, such that given the labels of any two vertices $u,v\in
V$ and of the edges in $E^{\prime}\subseteq E$, one can correctly determine,
with high probability, if $u$ and $v$ are connected in $G-E^{\prime}$. Note
that the label length is independent of $|E^{\prime}|$, the number of faulty
edges.

####  4.1.1 Labeling Scheme for $f=o(\log\log n)$

Parter and Petruschka [PP22] gave a recursive construction of labels for $f$
_vertex_ faults, by combining the sparse vertex-connectivity certificates of
[NI92] with the labels for edge faults of [DP21]. The sparsification of
Theorem 4.2 allows us to extend this technique to handle color faults.

######  Lemma 4.4.

There is a randomized labeling scheme for connectivity under $\leq f$ color
faults, assigning labels of length
${O}(fn^{1-1/2^{f}}\operatorname{polylog}(fn))$ bits on $n$-vertex graphs.

The idea is to construct labels for $f$ color faults by combining the labels
for edge faults of Dory-Parter [DP21] (Theorem 4.3) with recursively defined
labels for $f-1$ faults. To this end, we classify the colors according to
their _prevalence_ in the given input graph $G$. Let $\mathcal{H}$ be the set
of _high prevalence_ colors consisting of every color $c$ that appears at
least $\Delta=\Delta(n,f)$ times in $G$, where $\Delta$ is a threshold to be
optimized later. Let $\mathcal{R}$ denote the rest of the colors, not in
$\mathcal{H}$, that have _low prevalence_. At a high level, the failure of any
color with high prevalence $c\in\mathcal{H}$ is handled by recursively
invoking labels for $f-1$ color faults, but in the graph $G-c$. The
complementary case, where all failing colors have low prevalence, is treated
using the edge labels of [DP21], which are crucially capable of handling any
number of individual edge faults.

We use the following notations. Let $G^{\prime}$ be a subgraph of $G$. The
function $L_{f-1}(\cdot,G^{\prime})$ denotes the labels assigned to the
vertices and colors of $G^{\prime}$ by the (recursively defined) labeling
scheme for $f-1$ color faults. The function
$L_{\mathsf{E\text{-}faults}}(\cdot,G^{\prime})$ denotes the labels assigned
to the vertices and edges of $G^{\prime}$ by the labeling scheme of Theorem
4.3. For a color $c$ in $G$, let $E_{c}\subseteq E$ be the subset of $G$-edges
with color $c$.

Labeling. The labeling procedure is presented as Algorithm 1. The labels
$L_{1}(\cdot,G)$ (the base case $f=1$) are given by Theorem 3.5.

Algorithm 1 Creating the labels

1:Colored $n$-vertex graph $G$, fault parameter $f\geq 2$

2:Labels $L_{f}(v,G)$ for each vertex $v\in V$, and $L_{f}(c,G)$ for each
color $c$

3:$\Delta\leftarrow\Delta(n,f)$ $\triangleright$ prevalence threshold

4:$\mathcal{H}\leftarrow$ set of colors $c$ with $|E_{c}|\geq\Delta$

5:$\mathcal{R}\leftarrow$ set of colors $c$ with $|E_{c}|<\Delta$

6:for each vertex $v\in V$ do $\triangleright$ create the label $L_{f}(v,G)$

7: store in $L_{f}(v,G)$ the labels $L_{f-1}(v,G-h)$ for every
$h\in\mathcal{H}$

8: store in $L_{f}(v,G)$ the label $L_{\mathsf{E\text{-}faults}}(v,G)$

9:for each color $c$ do $\triangleright$ create the label $L_{f}(c,G)$

10: store in $L_{f}(c,G)$ the labels $L_{f-1}(c,G-h)$ for every
$h\in\mathcal{H}$

11: if $c\in\mathcal{R}$ then

12: store in $L_{f}(c,G)$ the labels $L_{\mathsf{E\text{-}faults}}(e,G)$ of
every $e\in E_{c}$

Answering queries. Let $u,v\in V$, and let $F$ be a set of at most $f$ colors.
Given $L(u),L(v)$ and $\\{L(c)\mid c\in F\\}$, we should determine if $u$ and
$v$ are connected in $G-F$. There are two cases:

  1. 1.

If $F\cap\mathcal{H}\neq\emptyset$: Let $h\in F\cap\mathcal{H}$, and denote
$F^{\prime}=F-\\{h\\}$. Note that $|F^{\prime}|\leq f-1$. The
$L_{f-1}(\cdot,G-h)$-labels of $u,v$ and of every $c\in F^{\prime}$ are stored
in their respective $L_{f}(\cdot,G)$-labels. By induction, we use these to
determine (w.h.p) if $u,v$ are connected in $(G-h)-F^{\prime}=G-F$.

  2. 2.

If $F\cap\mathcal{H}=\emptyset$: Then $F\subseteq\mathcal{R}$, so for every
$c\in F$, the labels $L_{\mathsf{E\text{-}faults}}(e,G)$ of every $e\in E_{c}$
are found in $L_{f}(c,G)$. The $L_{\mathsf{E\text{-}faults}}(\cdot,G)$-labels
of $u,v$ are found in their respective $L_{f}(\cdot,G)$-labels. By Theorem
4.3, using these we can determine (w.h.p) if $u,v$ are connected in
$G-\bigcup_{c\in F}E_{c}=G-F$.

Length analysis. Without loss of generality, we may assume that $G$ has
$O(fn\log(fn))$ edges; otherwise, we can replace $G$ by its subgraph given by
Theorem 4.2. Since $|E(G)|=O(fn\log(fn))$, then
$|\mathcal{H}|=O(\Delta^{-1}fn\log(fn)))$. Let $b(n,f-1)$ be a bound on the
bit-length of an $L_{f-1}(\cdot,\cdot)$ label assigned for an $n$-vertex
graph. Define $b(n,f)$ similarly for $L_{f}(\cdot,\cdot)$. The largest
$L_{f}(\cdot,G)$-labels are given for colors from $\mathcal{R}$: they store
$|\mathcal{H}|$ of the $L_{f-1}(\cdot,\cdot)$-labels and $\Delta$ of the
$L_{\mathsf{E\text{-}faults}}(\cdot,\cdot)$ labels. This gives the following
recursion:

$b(n,f)=O\big{(}b(n,f-1)\cdot\Delta^{-1}fn\log(fn)+\left(\log^{3}n+\log(fn)\right)\cdot\Delta\big{)}.$

To minimize the sum, we set $\Delta$ to make both terms equal, so that:

$\Delta=\Delta(n,f)=\sqrt{fn\log(fn)b(n,f-1)/(\log^{3}n+\log(fn))},$
$b(n,f)=O\left(\sqrt{b(n,f-1)fn\log(fn)\left(\log^{3}n+\log(fn)\right)}\right).$

Solving this recursion, with base case $b(n,1)=O(\sqrt{n}\log n)$ given by
Theorem 3.5, yields

$b(n,f)=O\left(\left[fn\log(fn)(\log^{3}n+\log(fn))\right]^{1-1/2^{f}}\right).$

This concludes the proof of Lemma 4.4 for the edge-colored case. The proof
extends easily to vertex-colored graphs, by classifying a color $c$ as having
high prevalence if the _volume_ (sum of degrees) of the set of vertices with
color $c$ is above the threshold $\Delta$.

####  4.1.2 Labeling Scheme for $f=\Omega(\log\log n)$

######  Lemma 4.5.

There is a randomized labeling scheme for connectivity under $f$ color faults,
assigning labels of length ${O}(n\cdot\operatorname{polylog}(fn))$ bits on
$n$-vertex graphs.

###### Proof.

Let $G=(V,E)$ be the input colored $n$-vertex graph with colors from $[C]$. By
Theorem 4.2, we may assume that $G$ has $\tilde{O}(fn)$ edges. For a color
$c$, denote by $E_{c}\subseteq E$ the set of edges with color $c$, and let
$T_{c}$ be a spanning forest of the subgraph $(V,E_{c})$. Finally, let
$H=\bigcup_{c\in[C]}T_{c}$. We show that for all $F\subseteq[C]$, every pair
of vertices are connected in $H-F$ iff they are connected in $G-F$. It
suffices to prove that if $e=\\{u,v\\}$ is an edge of $G-F$, then there is
some $u$-$v$ path in $H-F$. If $e$ has color $c\notin F$, then by construction
of $T_{c}$, there is a $c$-colored path in this forest connecting $u$ and $v$,
which is also present in $H-F$.

Labeling. Apply the Dory-Parter [DP21] scheme of Theorem 4.3 on $H$, resulting
in labels for the vertices and edges of $H$, denoted
$L_{\mathsf{E\text{-}faults}}(\cdot,H)$. The label $L(v)$ of a vertex $v\in V$
simply stores $L_{\mathsf{E\text{-}faults}}(v,H)$. The label $L(c)$ of a color
$c$ stores $L_{\mathsf{E\text{-}faults}}(e,H)$ of _every_ edge $e\in
E(T_{c})$. The claimed length bound is immediate, as storing a single
$L_{\mathsf{E\text{-}faults}}(\cdot,H)$-label requires $O(\log^{3}n+\log(fn))$
bits, and $|E(T_{c})|\leq n-1$.

Answering queries. Let $u,v\in V$ and $F\subseteq[C]$. The labels $L(u)$,
$L(v)$ and $\\{L(c)\mid c\in F\\}$, stores the
$L_{\mathsf{E\text{-}faults}}(\cdot,H)$-labels of $u,v$ and every
$e\in\bigcup_{c\in F}E(T_{c})$. Using these, we can, with high probability,
determine the connectivity of $u,v$ in $H-\bigcup_{c\in F}E(T_{c})=H-F$, and
hence also in $G-F$, with high probability.

The proof extends to vertex colors, where $E_{c}$ is the set of edges that
touch the color $c$. ∎

Theorem 4.1 follows by combining Lemma 4.4 and Lemma 4.5.

###  4.2 Lower Bound

We next provide a lower bound that generalizes the $\Omega(\sqrt{n})$-bit
lower bound for the case $f=1$ of Theorem 3.6. However, in contrast to Theorem
3.6, this lower bound is _existential_ , namely, it relies on some specific
‘worst-case’ topology.

######  Theorem 4.6.

Let $f\geq 1$ be a fixed constant. Every (possibly randomized) labeling scheme
for connectivity under $f$ color faults in $n$-vertex graphs must have label
length of $\Omega(n^{1-1/(f+1)})$ bits. Furthermore, this bound holds even for
labeling schemes restricted to simple planar graphs.

###### Proof.

Suppose there is such a labeling scheme with label length of $b$ bits. The
proof strategy is similar to the proof of Theorem 3.6: using the labeling
scheme to devise a one-way communication protocol for the indexing problem
$\textsc{Index}(N)$, with $N=\Theta(n)$. Let $x=x_{0}x_{1}\cdots x_{N-1}$ be
the input string of Alice, and $i^{*}\in[0,N)$ be the input index of Bob.

The communication protocol relies on a specific (uncolored) $n$-vertex graph
topology $G$, known in advance to Alice and Bob, which we now define. First,
denote

$M\stackrel{{\scriptstyle\operatorname{def}}}{{=}}\binom{N^{1/(f+1)}}{f}=\Theta(N^{1-1/(f+1)}).$

The topology $G$ is an “$f$-thick spider” with $N/M=\Theta(N^{1/(f+1)})$ arms,
each of length $M$. Formally, it consists of a starting vertex $s$, from which
there are $N/M$ emanating “$f$-thick” paths $P_{0},P_{1},\dots,P_{N/M-1}$,
where two consecutive vertices in a path have $f$ parallel edges between them.
Each such path $P_{k}$ consists of $M+1$ vertices, and is disjoint from the
other paths except for the common starting vertex $s$. We denote the vertex of
distance $l$ from $s$ in the path $P_{k}$ by $v_{k,l}$, so $s=v_{k,0}$. We
also use the shorthand notation $t_{k}=v_{k,M}$ for the last vertex of path
$P_{k}$. The set of $f$ parallel edges between $v_{k,l}$ and $v_{k,l+1}$ is
denoted by $E_{k,l}$. See Figure 1(Left) for an illustration.

Figure 1:  Illustration of the proof of Theorem 4.6. Left: The “$f$-thick
spider” graph topology $G$. Right: The coloring procedure for $E_{k,l}$.

Consider the color-palette $\\{0,1,\dots,N^{1/(f+1)}-1\\}\cup\\{\perp\\}$,
where $\perp$ is a never-failing null color. By its definition, $M$ is the
number of $f$-subsets of the color-set. Fix a bijection $F$ mapping
$l\in[0,M)$ to a unique $f$-subset of colors
$F(l)\subseteq\\{0,\dots,N^{1/(f+1)}-1\\}$. (The bijection $F$ is also part of
the protocol, i.e., known in advance to Alice and Bob.)

We are now ready to describe the protocol. Alice colors her copy of $G$
according to her input $x$, as follows. For each $k\in[0,N/M)$ and
$l\in[0,M)$, Alice considers the corresponding index $i=kM+l$. If $x_{i}=1$,
she colors each of the $f$ edges in $E_{k,l}$ with a distinct color from the
$f$ colors in $F(l)$. Otherwise, when $x_{i}=0$, she colors all of $E_{k,l}$
with the null color $\perp$. See illustration in Figure 1(Right).

This coloring procedure ensures the following property. Let $k$, $l$ and $i$
as before, and consider $P_{k}-F(l)$ (i.e., path $P_{k}$ after all $f$ colors
in $F(l)$ fail). For $l^{\prime}\neq l$, the edge-set $E_{k,l^{\prime}}$ has
at least one surviving edge: it is either entirely colored with the non-
failing $\perp$, or it contains all $f$ colors of $F(l^{\prime})$, of which at
least one is non-faulty as $F(l^{\prime})\neq F(l)$. Therefore, $P_{k}-F(l)$
is connected iff $v_{k,l}$ connects to $v_{k,l+1}$ after all $f$ colors in
$F(l)$ fail, which happen iff $x_{i}=0$.

Next, Alice assigns labels using the assumed labeling scheme, and sends to Bob
the labels of the vertices $s$ and $t_{0},\dots,t_{N/M-1}$, and the labels of
the colors $0,1,\dots,N^{1/(f+1)}-1$. To recover $x_{i^{*}}$, Bob decomposes
$i^{*}$ as $i^{*}=k^{*}\cdot M+l^{*}$ with $k^{*}\in[0,N/M)$, $l^{*}\in[0,M)$,
and uses the received labels of $s,t_{k^{*}}$ and the $f$ colors in $F(l^{*})$
to query the connectivity of $s$ and $t_{k^{*}}$ in $G-F(l^{*})$. If the
answer is _disconnected_ , Bob determines that $x_{i^{*}}=1$, and if it is
_connected_ , he determines that $x_{i^{*}}=0$. This establishes the protocol.
The correctness is guaranteed by the previously described property of the
coloring. The total number of bits sent by Alice is $O(bN^{1/(f+1)})$. Thus,
by Lemma 2.1, $O(bN^{1/(f+1)})=\Omega(N)$, and hence
$b=\Omega(N^{1-1/(f+1)})=\Omega(n^{1-1/(f+1)})$.

Finally, for the ‘furthermore’ part, we can alter $G$ by subdividing the
edges, i.e., replacing each edge with a length-two path which is colored
according to the original color of its corresponding edge in the $f$-thick
spider. The resulting graph is simple and planer, and the number of vertices
only increases by a factor of $O(f)=O(1)$, so it remains $\Theta(N)$, and the
proof goes through.

The proof for vertex-colored graphs also follows by subdividing the edges in
the above manner, where new vertices get the color of their corresponding
original edge, and original vertices get the color $\perp$. ∎

We note that in some sense, the proof technique of Theorem 4.6 cannot be used
to obtain a lower bound stronger than $\tilde{\Omega}(n^{1-1/(f+1)})$. See
Appendix E for a further discussion on this limitation.

##  5 Two Color Faults in Small-Diameter Graphs

In this section, we provide a nearly optimal labeling scheme under two color
faults for graphs with diameter $D=\tilde{O}(1)$.

###  5.1 Upper Bound

######  Theorem 5.1.

There is a deterministic labeling scheme for connectivity with two color
faults that, when given an $n$-vertex graph $G$ with all connected components
of diameter at most $D$, assigns labels of length $O(D(\sqrt{n}+D)\log^{2}n)$
bits.

###### Proof.

We focus on the case where $G$ is connected, and later mention the
straightforward modifications to obtain the general case. We use the following
notation. For a color $c\in[C]$ and a subgraph $H$ of $G$, the notation $c\in
H$ means that $c$ appears in $H$. When $H$ is a tree, and $u,v\in V(H)$, the
unique $u$-$v$ path in $H$ is denoted by $H[u,v]$.

Preprocessing. Our labeling relies on several trees formed by executing
breadth-first search procedures (in short, BFS trees), which we now define.
First, let $T$ be a BFS tree in $G$, rooted at the vertex $s$ with minimum
$\mathsf{id}$. Next, for each $v\in V$ and color $c\in T[s,v]$, we let
$T_{v,c}$ be the tree formed by executing a BFS procedure from $v$ in $G-c$,
but halting once $\sqrt{n}$ vertices are reached. Note that if $T_{v,c}$
contains fewer than $\sqrt{n}$ vertices, then it is a spanning tree for the
connected component of $v$ in $G-c$. However, if $T_{v,c}$ has $\sqrt{n}$
vertices, it might not span this entire component. We next compute a _hitting
set_ $U\subseteq V$ for the trees $T_{v,c}$ that have $\sqrt{n}$ vertices.
That is, for every $v\in V$ and $c\in T[s,v]$, if $T_{v,c}$ contains
$\sqrt{n}$ vertices, then it contains some vertex $u_{v,c}\in U$. It is well
known that such a hitting set $U$ with $|U|=O(\sqrt{n}\log n)$ can be
constructed efficiently (e.g., using the greedy algorithm). For completeness,
we include a proof in Appendix F (Lemma F.1).

Labeling. The label $L(v)$ of a vertex $v\in V$ is constructed by Algorithm 2.
The label $L(c)$ of a color $c\in[C]$ is constructed by Algorithm 3.

Algorithm 2 Creating the label $L(v)$ of vertex $v\in V$

1:for each color $c\in T[s,v]$ do

2: store $\mathsf{cid}(v,G-c)$

3: store $\mathsf{cid}(v,G-\\{c,d\\})$ for every color $d\in T_{v,c}$

4: if $T_{v,c}$ has $\sqrt{n}$ vertices then

5: $u_{v,c}\leftarrow$ a vertex from $U$ present in $T_{v,c}$

6: store $\mathsf{id}(u_{v,c})$

7: store $\mathsf{cid}(u_{v,c},G-\\{c,d\\})$ for every $d\in T[s,u_{v,c}]$

Algorithm 3 Creating the label $L(c)$ of color $c\in[C]$

1:for each vertex $u\in U$ do

2: for each color $d\in T[s,u]$ do

3: store $\mathsf{cid}(u,G-\\{c,d\\})$

Length analysis. Recall that $T$ is a BFS tree for $G$, so its depth is at
most $D$. As $|U|=O(\sqrt{n}\log n)$, we obtain that a color label $L(c)$
stores $O(D\sqrt{n}\log^{2}n)$ bits. Consider now a vertex label $L(v)$. Note
that $T[s,v]$ has at most $D$ edges. For every $c\in T[s,v]$, we have that
$T_{v,c}$ has at most $\sqrt{n}$ edges, and $T[s,u_{v,c}]$ (when defined) has
at most $D$ edges. Therefore, the label $L(v)$ stores only
$O(D\cdot(\sqrt{n}+D))$ $\mathsf{cid}$s, which requires $O(D(\sqrt{n}+D)\log
n)$ bits. In total, all labels store $O(D(\sqrt{n}+D)\log^{2}n)$ bits.

Answering queries. Given the labels $L(v),L(c),L(d)$ of $v\in V$ and two
colors $c,d\in[C]$, we show a procedure for deducing
$\mathsf{cid}(v,G-\\{c,d\\})$.

If both $c$ and $d$ do not appear on $T[s,v]$, then
$\mathsf{cid}(v,G-\\{c,d\\})=\mathsf{cid}(s,G-\\{c,d\\})=\mathsf{id}(s)$,
where the last equality is by choice of $s$ as the vertex with minimum
$\mathsf{id}$, and we are done (as the minimum $\mathsf{id}$ can be assumed to
be fixed, say to $1$). From now on, assume that one of the failing colors, say
$c$, appears on $T[s,v]$. If $d\in T_{v,c}$, then
$\mathsf{cid}(v,G-\\{c,d\\})$ is found in $L(v)$, and we are done. So, assume
further that $d\notin T_{v,c}$.

We now treat the case where $T_{v,c}$ has fewer than $\sqrt{n}$ vertices. Then
$T_{v,c}$ spans the connected component of $v$ in $G-c$. As $d\notin T_{v,c}$,
it must be that this is also the connected component of $v$ in $G-\\{c,d\\}$.
Therefore, $\mathsf{cid}(v,G-\\{c,d\\})=\mathsf{cid}(v,G-c)$, and the latter
is stored in $L(v)$, so we are done.

Next, we handle the case where $T_{v,c}$ has $\sqrt{n}$ vertices, so $u_{v,c}$
is defined. As $d\notin T_{v,c}$, and also $c\notin T_{v,c}$ (by definition),
the path $T_{v,c}[v,u_{v,c}]$ connects $v$ and $u_{v,c}$ in $G-\\{c,d\\}$,
implying that $\mathsf{cid}(v,G-\\{c,d\\})=\mathsf{cid}(u_{v,c},G-\\{c,d\\})$
and therefore it is enough to show how to find
$\mathsf{cid}(u_{v,c},G-\\{c,d\\})$. There are three options:

  1. 1.

If $c,d\notin T[s,u_{v,c}]$, then
$\mathsf{cid}(u_{v,c},G-\\{c,d\\})=\mathsf{cid}(s,G-\\{c,d\\})=\mathsf{id}(s)$.

  2. 2.

If $c\in T[s,u_{v,c}]$, then $L(d)$ stores
$\mathsf{cid}(u_{v,c},G-\\{c,d\\})$.

  3. 3.

If $d\in T[s,u_{v,c}]$, then $L(v)$ stores
$\mathsf{cid}(u_{v,c},G-\\{c,d\\})$.

As at least one of these options must hold, this concludes the proof for
connected graphs.

To handle graphs with several connected components, the proof is modified by
replacing the single BFS tree $T$ with a collection of BFS trees, one for each
connected component of $G$.

The proof works as-is also for vertex-colored graphs. ∎

###  5.2 Lower Bounds

We now show that Theorem 5.1 is optimal for graphs with $D=\tilde{O}(1)$.

######  Theorem 5.2.

Let $G$ be a graph topology and $H$ be a subgraph of $G$. Then, every labeling
scheme for connectivity under two color faults in (colorings of) $G$ must have
label length of $\Omega(\mathsf{bp}(H))$ bits.

###### Proof.

The proof is by a reduction. We use connectivity labels for _two_ color faults
in $G$, denoted $L_{G,2}(\cdot)$, to construct such labels for _one_ color
fault in $H$, denoted $L_{H,1}(\cdot)$, as follows. Given a coloring of $H$
with palette $[C]$, we extend it to a coloring of $G$ by assigning to all
edges of $G$ that are not in $H$ a new fixed color $c^{\prime}\notin[C]$. The
label $L_{H,1}(v)$ of each vertex $v\in V(H)$ simply stores $L_{G,2}(v)$. The
label of $L_{H,1}(c)$ of a color $c\in[C]$ stores the pair
$\left<L_{G,2}(c),L_{G,2}(c^{\prime})\right>$. Thus, given the
$L_{H,1}(\cdot)$ labels of $u,v\in V(H)$ and $c\in[C]$, one can use the
$L_{G,2}(\cdot)$ labels stored in them to decide if $u,v$ are connected in
$G-\\{c,c^{\prime}\\}$, which happens iff $u,v$ are connected in $H-c$. By
Theorem 3.6, the $L_{H,1}(\cdot)$ labels must have maximum length
$\Omega(\mathsf{bp}(H))$, which implies the same conclusion for the
$L_{G,2}(\cdot)$ labels. ∎

######  Corollary 5.3.

For every $n$, there exists a graph $G$ on $n$ vertices with
$\operatorname{diam}(G)=2$, for which every connectivity labeling scheme under
two color faults must have labels of length $\Omega(\sqrt{n})$.

###### Proof.

Let $G$ be the wheel graph on $n$ vertices, composed of a cycle $C$ on $n-1$
vertices, and another vertex with an edge going to each of them. The result
follows from Theorem 5.2 as $\operatorname{diam}(G)=2$, and
$\mathsf{bp}(C)=\Omega(\sqrt{n})$. ∎

##  6 Conclusion

In this work, we introduced $f$ color fault-tolerant connectivity labeling
schemes, which generalize the well-studied edge/vertex fault-tolerant
connectivity labeling schemes. Our results settle the complexity of the
problem when $f=1$. For $f\geq 2$, many interesting open problems remain:

  * •

Can we close the gap between the $\tilde{O}(n^{1-1/2^{f}})$ and
$\Omega(n^{1-1/(f+1)})$ bounds? Concretely, is there a labeling scheme for
connectivity under $f=2$ color faults with labels of $\tilde{O}(n^{2/3})$
bits? Can our solution for low-diameter graphs be utilized to obtain such a
scheme?

  * •

Is there a graph parameter that generalizes $\mathsf{bp}(G)$ and characterizes
the length of a universally optimal labeling scheme for $f\geq 2$? Notably,
the proof of Theorem 5.2 implies that even very simple graphs with small
diameter and ball packing number admit a lower bound of $\Omega(\sqrt{n})$
bits for $f=2$.

  * •

Can we provide non-trivial _centralized oracles_ for connectivity under $f\geq
2$ color faults?

  * •

Are there routing schemes for avoiding $f\geq 2$ forbidden colors with small
header size? Our labeling scheme for $f\geq 2$ could be extended to such a
routing scheme, but with a large header size of $\tilde{O}(n^{1-1/2^{f}})$
bits.

Another intriguing direction is going beyond connectivity queries; a natural
goal is to additionally obtain approximate distances, which is open even for
$f=1$. This problem is closely related to providing forbidden color routing
schemes with good stretch guarantees.

##### Acknowledgments.

We are grateful to Merav Parter for encouraging this collaboration, and for
helpful guidance and discussions.

## References

  * [ACG12] Ittai Abraham, Shiri Chechik, and Cyril Gavoille.  Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels.  In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC, pages 1199–1218. ACM, 2012.  doi:10.1145/2213977.2214084.
  * [ACGP16] Ittai Abraham, Shiri Chechik, Cyril Gavoille, and David Peleg.  Forbidden-set distance labels for graphs of bounded doubling dimension.  ACM Trans. Algorithms, 12(2):22:1–22:17, 2016.  doi:10.1145/2818694.
  * [ACIM99] Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani.  Fast estimation of diameter and shortest paths (without matrix multiplication).  SIAM J. Comput., 28(4):1167–1181, 1999.  doi:10.1137/S0097539796303421.
  * [BBP22] Surender Baswana, Koustav Bhanja, and Abhyuday Pandey.  Minimum+1 (s, t)-cuts and dual edge sensitivity oracle.  In 49th International Colloquium on Automata, Languages, and Programming, ICALP, volume 229 of LIPIcs, pages 15:1–15:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.ICALP.2022.15.
  * [BGPW17] Greg Bodwin, Fabrizio Grandoni, Merav Parter, and Virginia Vassilevska Williams.  Preserving distances in very faulty graphs.  In 44th International Colloquium on Automata, Languages, and Programming, ICALP, volume 80 of LIPIcs, pages 73:1–73:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.  doi:10.4230/LIPIcs.ICALP.2017.73.
  * [CDP+07] David Coudert, Pallab Datta, Stephane Perennes, Hervé Rivano, and Marie-Emilie Voge.  Shared risk resource group complexity and approximability issues.  Parallel Process. Lett., 17(2):169–184, 2007.  doi:10.1142/S0129626407002958.
  * [CGKT08] Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté, and Andrew Twigg.  Connectivity check in 3-connected planar graphs with obstacles.  Electron. Notes Discret. Math., 31:151–155, 2008.  doi:10.1016/j.endm.2008.06.030.
  * [Che12] Shiri Chechik.  Improved distance oracles and spanners for vertex-labeled graphs.  In Algorithms - ESA 2012 - 20th Annual European Symposium, volume 7501 of Lecture Notes in Computer Science, pages 325–336. Springer, 2012.  doi:10.1007/978-3-642-33090-2\\_29.
  * [Cho16] Keerti Choudhary.  An optimal dual fault tolerant reachability oracle.  In 43rd International Colloquium on Automata, Languages, and Programming, ICALP, volume 55 of LIPIcs, pages 130:1–130:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.  doi:10.4230/LIPIcs.ICALP.2016.130.
  * [CT07] Bruno Courcelle and Andrew Twigg.  Compact forbidden-set routing.  In Proceedings 24th Annual Symposium on Theoretical Aspects of Computer Science, STACS, volume 4393 of Lecture Notes in Computer Science, pages 37–48. Springer, 2007.  doi:10.1007/978-3-540-70918-3\\_4.
  * [DP09] Ran Duan and Seth Pettie.  Dual-failure distance and connectivity oracles.  In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 506–515, 2009.  doi:10.1137/1.9781611973068.56.
  * [DP21] Michal Dory and Merav Parter.  Fault-tolerant labeling and compact routing schemes.  In ACM Symposium on Principles of Distributed Computing, PODC, pages 445–455, 2021.  doi:10.1145/3465084.3467929.
  * [EBR+03] Georgios Ellinas, Eric Bouillet, Ramu Ramamurthy, J.-F Labourdette, Sid Chaudhuri, and Krishna Bala.  Routing and restoration architectures in mesh optical networks.  Opt Networks Mag, 4, 01 2003.
  * [EFW21] Jacob Evald, Viktor Fredslund-Hansen, and Christian Wulff-Nilsen.  Near-optimal distance oracles for vertex-labeled planar graphs.  In 32nd International Symposium on Algorithms and Computation, ISAAC, volume 212 of LIPIcs, pages 23:1–23:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.ISAAC.2021.23.
  * [FPZ23] Kyle Fox, Debmalya Panigrahi, and Fred Zhang.  Minimum cut and minimum _k_ -cut in hypergraphs via branching contractions.  ACM Trans. Algorithms, 19(2):13:1–13:22, 2023.  doi:10.1145/3570162.
  * [GK17] Manoj Gupta and Shahbaz Khan.  Multiple source dual fault tolerant BFS trees.  In 44th International Colloquium on Automata, Languages, and Programming, ICALP, volume 80 of LIPIcs, pages 127:1–127:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.  doi:10.4230/LIPIcs.ICALP.2017.127.
  * [GKP17] Mohsen Ghaffari, David R. Karger, and Debmalya Panigrahi.  Random contractions and sampling for hypergraph and hedge connectivity.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1101–1114, 2017.  doi:10.1137/1.9781611974782.71.
  * [GLMW18] Pawel Gawrychowski, Gad M. Landau, Shay Mozes, and Oren Weimann.  The nearest colored node in a tree.  Theor. Comput. Sci., 710:66–73, 2018.  doi:10.1016/j.tcs.2017.08.021.
  * [HLWY11] Danny Hermelin, Avivit Levy, Oren Weimann, and Raphael Yuster.  Distance oracles for vertex-labeled graphs.  In Automata, Languages and Programming - 38th International Colloquium, ICALP, volume 6756 of Lecture Notes in Computer Science, pages 490–501. Springer, 2011.  doi:10.1007/978-3-642-22012-8\\_39.
  * [Hu03] Jian Qiang Hu.  Diverse routing in optical mesh networks.  IEEE Transactions on Communications, 51(3):489–494, 2003.  doi:10.1109/TCOMM.2003.809779.
  * [HWZ21] Bernhard Haeupler, David Wajc, and Goran Zuzic.  Universally-optimal distributed algorithms for known topologies.  In 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 1166–1179, 2021.  doi:10.1145/3406325.3451081.
  * [IEWM23] Taisuke Izumi, Yuval Emek, Tadashi Wadayama, and Toshimitsu Masuzawa.  Deterministic fault-tolerant connectivity labeling scheme.  In Symposium on Principles of Distributed Computing, PODC, pages 190–199. ACM, 2023.  doi:10.1145/3583668.3594584.
  * [JKS08] T. S. Jayram, Ravi Kumar, and D. Sivakumar.  The one-way communication complexity of hamming distance.  Theory Comput., 4(1):129–135, 2008.  doi:10.4086/toc.2008.v004a006.
  * [Joh74] David S. Johnson.  Approximation algorithms for combinatorial problems.  Journal of Computer and System Sciences, 9(3):256–278, 1974.  doi:10.1016/S0022-0000(74)80044-9.
  * [KN96] Eyal Kushilevitz and Noam Nisan.  Communication Complexity.  Cambridge University Press, 1996.  doi:10.1017/CBO9780511574948.
  * [KNR99] Ilan Kremer, Noam Nisan, and Dana Ron.  On randomized one-round communication complexity.  Comput. Complex., 8(1):21–49, 1999.  doi:10.1007/s000370050018.
  * [Kui12] F. Kuipers.  An overview of algorithms for network survivability.  ISRN Communications and Networking, 2012, 12 2012.  doi:10.5402/2012/932456.
  * [LM19] Itay Laish and Shay Mozes.  Efficient dynamic approximate distance oracles for vertex-labeled planar graphs.  Theory Comput. Syst., 63(8):1849–1874, 2019.  doi:10.1007/s00224-019-09949-5.
  * [Lov75] László Lovász.  On the ratio of optimal integral and fractional covers.  Discret. Math., 13(4):383–390, 1975.  doi:10.1016/0012-365X(75)90058-8.
  * [MM96] S. Muthukrishnan and Martin Müller.  Time and space efficient method-lookup for object-oriented programs.  In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 42–51, 1996.  URL: http://dl.acm.org/citation.cfm?id=313852.313882.
  * [MN02] Eytan H. Modiano and Aradhana Narula-Tam.  Survivable lightpath routing: a new approach to the design of wdm-based networks.  IEEE J. Sel. Areas Commun., 20(4):800–809, 2002.  doi:10.1109/JSAC.2002.1003045.
  * [NI92] Hiroshi Nagamochi and Toshihide Ibaraki.  A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph.  Algorithmica, 7(5&6):583–596, 1992.  doi:10.1007/BF01758778.
  * [Par15] Merav Parter.  Dual failure resilient BFS structure.  In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC, pages 481–490, 2015.  doi:10.1145/2767386.2767408.
  * [Par20] Merav Parter.  Distributed constructions of dual-failure fault-tolerant distance preservers.  In 34th International Symposium on Distributed Computing, DISC, volume 179 of LIPIcs, pages 21:1–21:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.DISC.2020.21.
  * [PP13] Merav Parter and David Peleg.  Sparse fault-tolerant BFS trees.  In Algorithms - ESA 2013 - 21st Annual European Symposium, volume 8125 of Lecture Notes in Computer Science, pages 779–790. Springer, 2013.  doi:10.1007/978-3-642-40450-4\\_66.
  * [PP22] Merav Parter and Asaf Petruschka.  Õptimal dual vertex failure connectivity labels.  In 36th International Symposium on Distributed Computing, DISC, volume 246 of LIPIcs, pages 32:1–32:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.DISC.2022.32.
  * [PPP23] Merav Parter, Asaf Petruschka, and Seth Pettie.  Connectivity labeling for multiple vertex failures.  2023\.  arXiv:2307.06276.
  * [PST24] Asaf Petruschka, Shay Sapir, and Elad Tzalik.  Color fault-tolerant spanners.  In 15th Innovations in Theoretical Computer Science Conference, ITCS, volume 287 of LIPIcs, pages 88:1–88:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.  doi:10.4230/LIPICS.ITCS.2024.88.
  * [Tsu18] Dekel Tsur.  Succinct data structures for nearest colored node in a tree.  Inf. Process. Lett., 132:6–10, 2018.  doi:10.1016/j.ipl.2017.10.001.
  * [TZ01] Mikkel Thorup and Uri Zwick.  Compact routing schemes.  In Proceedings 13th ACM Symposium on Parallel Algorithms and Architectures, SPAA, pages 1–10, 2001.
  * [vEBKZ77] Peter van Emde Boas, R. Kaas, and E. Zijlstra.  Design and implementation of an efficient priority queue.  Math. Syst. Theory, 10:99–127, 1977.  doi:10.1007/BF01683268.
  * [Wil83] Dan E. Willard.  Log-logarithmic worst-case range queries are possible in space $\Theta(N)$.  Inf. Process. Lett., 17(2):81–84, 1983.  doi:10.1016/0020-0190(83)90075-3.
  * [XS20] Rupei Xu and Warren Shull.  Hedge connectivity without hedge overlaps.  2020\.  arXiv:2012.10600.
  * [ZCTZ11] Peng Zhang, Jin-Yi Cai, Lin-Qing Tang, and Wen-Bo Zhao.  Approximation and hardness results for label cut and related problems.  Journal of Combinatorial Optimization, 21:192–208, 2011.  doi:10.1007/s10878-009-9222-0.

##  Appendix A Reduction from All-Pairs to Single-Source

In the _single-source_ variant of fault-tolerant connectivity, the input graph
$G$ comes with a designated _source vertex_ $s$. The queries to be supported
are of the form $\left<u,F\right>$, where $u\in V$ and $F$ is a faulty set of
size at most $f$. It is required to report if $u$ is connected to the source
$s$ in $G-F$. The following result shows that this variant is equivalent to
the all-pairs variant, up to $\log n$ factors. The result holds whether the
faults are edges, vertices, or colors, hence we do not specify the type of
faults.

######  Theorem A.1.

Let $f\geq 1$. Suppose there is a (possibly randomized) single-source $f$
fault-tolerant connectivity labeling scheme that assigns labels of at most
$b(n,f)$ bits on every $n$-vertex graph. Then, there is a randomized all-pairs
$f$ fault-tolerant connectivity labeling scheme that assigns labels of length
$O(b(n+1,f)\cdot\log^{2}n)$ bits on every $n$-vertex graph.

###### Proof.

Labeling. For each $i,j$ with $1\leq i\leq\lceil\alpha\ln(n)/\ln(0.9)\rceil$,
$1\leq j\leq\lceil\log_{2}n\rceil+2$ we independently construct a graph
$G_{ij}$ as follows: Start with $G$, add a new vertex $s_{ij}$, and
independently for each $v\in V$, add a new edge connecting $s_{ij}$ to $v$
with probability $2^{-j}$. The vertex $s_{ij}$ and the new edges are treated
as _non-failing_. That is, in case of color faults, they get a null-color
$\perp$ that does not appear in $G$. For each element (vertex/edge/color) $x$
of $G$, its label $L(x)$ is the concatenation of all $L_{ij}(x)$, where the
$L_{ij}(\cdot)$ are the labels given by the single-source scheme to the
instance $G_{ij}$ with designated source $s_{ij}$. The claimed length bound is
immediate.

Answering queries. Let $u,w\in V$, and let $F$ be a fault-set of size at most
$f$. Given $L(u),L(w)$ and $\\{L(x)\mid x\in F\\}$, we should determine if
$u,w$ are connected in $G-F$. To this end, for each $i,j$, we use the
$L_{ij}(\cdot)$ labels of $u,F$ to determine if $u$ is connected to $s_{ij}$
in $G_{ij}$, and do the same with $w$ instead of $u$. If the answers are
always identical for $u$ and $w$, we output _connected_. Otherwise, we output
_disconnected_.

Analysis. We have made only $O(\log^{2}n)$ queries using the single-source
scheme, so, with high probability, all of these are answered correctly. Assume
this from now on.

If $u,w$ are connected in $G-F$, then this is also true for all $G_{ij}-F$, so
they must agree on the connectivity to $s_{ij}$ in this graph. Hence, in this
case, the answers for $u$ and $w$ are always identical, and we correctly
output _connected_.

Suppose now that $u$ and $w$ are disconnected in $G-F$. Let $U$ be the set of
vertices in $u$’s connected component in $G-F$. Define $W$ analogously for
$w$. Without loss of generality, assume $|U|\leq|W|$. Let $j$ be such that
$2^{j-2}<|U|\leq 2^{j-1}$. Let $N^{(i)}_{U}$ be the number of edges between
$s_{ij}$ and $U$ in $G_{ij}$, and define $N^{(i)}_{W}$ similarly. By Markov’s
inequality,

$\displaystyle\Pr\big{[}N^{(i)}_{U}=0\big{]}$ $\displaystyle\geq
1-\mathbb{E}\big{[}N^{(i)}_{U}\big{]}=1-|U|\cdot 2^{-j}\geq 1-2^{j-1}\cdot
2^{-j}=1/2.$ On the other hand, $\displaystyle\Pr[N^{(i)}_{W}\geq 1]$
$\displaystyle=1-\left(1-2^{-j}\right)^{|W|}\geq
1-\left(1-2^{-j}\right)^{2^{j-2}}\geq 1-e^{-1/4}>0.2.$

Since $U$ and $W$ are disjoint, $N^{(i)}_{U}$ and $N^{(i)}_{W}$ are
independent random variables. Hence, with probability at least $0.1$, the
source $s_{ij}$ is connected to $w$ but not to $u$ in $G_{ij}-F$, and the
answers for $u$ and $w$ given by the $L_{ij}(\cdot)$-labels are different. As
the graphs $\\{G_{ij}\\}_{i}$ are formed independently, the probability there
exists an $i$ for which $w$ is connected to $s_{ij}$ and $u$ is disconnected
from $s_{ij}$ is at least $1-(0.9)^{\alpha\ln n/\ln(0.9)}=1-1/n^{\alpha}$. In
this case, the output is _disconnected_ , as required. ∎

##  Appendix B Routing

In this section, we provide a routing scheme for avoiding any single forbidden
color. This is a natural extension of the forbidden-set routing framework,
initially introduced by [CT07] (see also [ACG12, ACGP16, DP21, PPP23]), to the
setting of colored graphs. We refer the reader to [DP21] for an overview of
forbidden-set routing, and related settings. Such a routing scheme consists of
two algorithms. The first is a preprocessing (centralized) algorithm that
computes _routing tables_ to be stored at each vertex of $G$, and _labels_ for
the vertices and the colors. The second is a distributed routing algorithm
that enables routing a message $M$ from a source vertex $s$ to a target vertex
$t$ avoiding edges of color $c$. Initially, the labels of $s,t,c$ are found in
the source $s$. Then, at each intermediate node $v$ in the route, $v$ should
use the information in its table, and in the (short) header of the message, in
order to determine where the message should be sent; formally, $v$ should
compute the _port number_ of the next edge to be taken from $v$ (which must
not be of color $c$). It may also edit the header for future purposes.

The main concern is minimizing the size of the tables and labels, and even
more so of the header (as it is communicated through the route). Another
important concern is optimizing the _stretch_ , which is the ratio between the
length of the routing path and the length of the shortest $s,t$ path in $G-c$.
Unfortunately, our routing scheme does not provide good stretch guarantees,
and optimizing the stretch is an interesting direction for future work. We
note, however, that the need to avoid edges of color $c$ by itself poses a
nontrivial challenge, and black-box application of the state-of-the-art
routings schemes of Dory and Parter [DP21] for avoiding $f=\Omega(n)$
individual edges would yield large labels, tables and headers, _and_ large
stretch (all become $\Omega(n)$). We show:

######  Theorem B.1.

There is a deterministic routing scheme for avoiding one forbidden color such
that, for a given colored $n$-vertex graph $G$, the following hold:

  * •

The routing tables stored at the vertices are all of size
$O(\mathsf{bp}(G)\log n)$ bits.

  * •

The labels assigned to the vertices and the colors are of size
$O(\mathsf{bp}(G)\log n)$ bits.

  * •

The header size required for routing a message contains only $O(\log n)$ bits.

The rest of the section is devoted to proving the above theorem. For the sake
of simplicity, we assume that when $c$ is the color to be avoided, the graph
$G-c$ is connected. (In particular, this also implies that $G$ is connected.)
Intuitively, this assumption is reasonable as we cannot route between
different connected components of $G-c$. To check if the routing is even
possible (i.e., if $s$ and $t$ are in the same connected component), we can
use the connectivity labels of Theorem 3.5 at the beginning of the procedure.
Technically, this assumption can be easily removed, at the cost of introducing
some additional clutter.

###  B.1 Basic Tools

In this section we provide several basic building blocks on which our scheme
is based.

##### Tree Routing.

The first required tool is the _Thorup-Zwick tree routing scheme_ [TZ01],
which we use in a black-box manner. Its properties are summarized in the
following lemma:

######  Lemma B.2 (Tree Routing [TZ01]).

Let $T$ be an $n$-vertex tree. One can assign each vertex $v\in V(T)$ a
_routing table_ $R_{T}(v)$ and a _destination label_ $L_{T}(v)$ with respect
to the tree $T$, both of $O(\log n)$ bits. For any two vertices $u,v\in V(T)$,
given $R_{T}(u)$ and $L_{T}(v)$, one can find the port number of the $T$-edge
from $u$ that heads in the direction of $v$ in $T$.

##### The Vertex Set $A$.

Our scheme crucially uses the existence of the set $A$ constructed in the
labeling procedure of Section 3.1. The following lemma summarizes its two
crucial properties:

######  Lemma B.3.

There is a vertex set $A\subseteq V$ such that $|A|=O(\mathsf{bp}(G))$, and
every vertex $v\in V$ has $\operatorname{dist}_{G}(v,A)=O(\mathsf{bp}(G))$.

##### Spanning Tree and Recovery Trees.

We next define several trees that are crucial for our scheme. First, we
construct a specific spanning tree $T$ of $G$, designed so that the $V$-to-$A$
shortest paths in $G$ are tree paths in $T$. Recall that for every $v\in V$,
$P(v)$ a shortest path connecting $v$ to $A$, and $a(v)$ is the $A$-endpoint
of this path (see the beginning of Section 3.1). We choose the paths $P(v)$
consistently, so that if vertex $u$ appears on $P(v)$, then $P(u)$ is a
subpath of $P(v)$. This ensures that the union of the paths $\bigcup_{v\in
V}P(v)$ is a forest. The tree $T$ is created by connecting the parts of this
forest by arbitrary edges. We root $T$ at an arbitrary vertex $r$.

After the failure of color $c$, the tree $T$ breaks into _fragments_ (the
connected components of $T-c$). We define the _recovery tree_ of color $c$,
denoted $T_{c}$, as a spanning tree of $G-c$ obtained by connecting the
fragments of $T-c$ via additional edges of $G-c$. These edges are called the
_recovery edges_ of $T_{c}$, and the fragments of $T-c$ are also called
fragments of $T_{c}$.

##### First Recovery Edges.

For $u,v\in V$ and color $c$, we denote $e(u,v,c)$ as the first recovery edge
appearing in the $u$-to-$v$ path in $T_{c}$ (when such exists). Note that we
treat this path as directed from $u$ to $v$. Accordingly, we think of
$e(u,v,c)$ as a _directed_ edge $(x,y)$ where its first vertex $x$ is closer
to $u$, and its second vertex $y$ is closer to $v$. Thus, $e(u,v,c)$ and
$e(v,u,c)$ refer to the same edge, but in opposite directions. We will use a
basic data block denoted $\mathsf{FirstRecEdge}(u,v,c)$ storing the following
information regarding $e(u,v,c)$:

  * •

The port number of $e(u,v,c)$, from its first vertex $x$ to its second vertex
$y$.

  * •

The tree-routing label w.r.t. $T$ of the first vertex $x$, i.e. $L_{T}(x)$.

  * •

A Boolean indicating whether the second vertex $y$ and $v$ lie in the same
fragment of $T-c$.

Note that $\mathsf{FirstRecEdge}(u,v,c)$ consists of $O(\log n)$ bits.

#####  $A$-fragments and $B$-fragments.

A fragment of $T-c$ containing at least one vertex from $A$ is called an _$A$
-fragment_. For convenience, the fragments that are not $A$-fragments (i.e.,
do not contain $A$-vertices) are called _$B$ -fragments_. Our construction of
$T$ ensures the following property:

######  Lemma B.4.

For every color $c$, if vertex $v\in V$ is in a $B$-fragment of $T-c$, then
$c\in P(v)$, i.e., the color $c$ appears on the path $P(v)$.

###### Proof.

By construction, the path $P(v)$ is a tree path in $T$ connecting $v$ to some
$a\in A$. As $v$ is in a $B$-fragment of $T-c$, this path cannot survive in
$T-c$, hence the color $c$ appears on it. ∎

###  B.2 High Level Overview of the Routing Scheme

Our scheme is best described via two special cases; in the first case, $t$ is
in an $A$-fragment, and in the second case, the $s$-to-$t$ path in $T_{c}$ is
only via $B$-fragments. We then describe how to connect between these two
cases, essentially by first routing to the $A$-fragment that is nearest to $t$
in $T_{c}$, and then routing from that $A$-fragment to $t$ (crucially, this
route does not contain $A$-fragments).

##### First Case: $t$ is in an $A$-fragment.

Suppose an even stronger assumption, that we are actually given a vertex
$a^{*}\in A$ that is in the same fragment as $t$. We will resolve this
assumption only at the wrap-up of this section. The general strategy is to try
and follow the $s$-to-$t$ path in the recovery tree $T_{c}$. This path is of
the form $P_{1}\circ e_{1}\circ P_{2}\circ e_{2}\circ\cdots\circ e_{\ell}\circ
P_{\ell}$, where each $P_{i}$ is a path in a fragment $X_{i}$ of $T-c$, and
the $e_{i}$ edges are recovery edges connecting between fragments, so that
$X_{\ell}$ is the fragment of $t$ in $T-c$. Rather than following this path
directly, our goal will be to route from one fragment to the next, through the
corresponding recovery edge.

As there are only $O(\mathsf{bp}(G))$ $A$-fragments, every $v\in V$ can store
$O(\log n)$ bits for each $A$-fragment. However, the routing table of $v$
cannot store said information for every color. To overcome this obstacle, note
that in every fragment in $T-c$ (besides the one containing the root $r$), the
root of the fragment is connected to its parent via a $c$-colored edge. We
leverage this property, and let the root of every fragment store, for every
$a\in A$, the first recovery edge $e(v,a,c)$ on the path from $v$ to $a$ in
$T_{c}$. Thus, when reaching the fragment $X_{i}$ of $T-c$, we first go up as
far as possible, until we hit the root of $X_{i}$. In the general case, this
is a vertex $v_{i}$ such that the edge to its parent is of color $c$.
Therefore, $v_{i}$ stores in its table the next recovery edge
$e_{i}=e(v_{i},a^{*},c)$ we aim to traverse. The special case of $v_{i}=r$ is
resolved using the color labels. The color $c$ stores, for every $a\in A$, the
first recovery edge $e(r,a,c)$; at the start of the routing procedure, $s$
extracts the information regarding $e(r,a^{*},c)$ and writes it in the header.

So, we discover $e_{i}$ in $v_{i}$, and next we use the Thorup-Zwick routing
of Lemma B.2 on $T$ to get to the first endpoint of $e_{i}$. The path leading
us to this endpoint is fault-free (it is contained in the fragment $X_{i}$).
Then, we traverse $e_{i}$, and continue in the same manner in the next
fragment $X_{i+1}$.

Once we reach the $A$-fragment that contains $a^{*}$ and $t$, we again use the
Thorup-Zwick routing of Lemma B.2 on $T$. For that we also need $L_{T}(t)$,
which $s$ can learn from the label of $t$ and write in the header at the
beginning of the procedure.

##### Second Case: the $s$-to-$t$ path in $T_{c}$ is only via $B$-fragments.

As every vertex $v$ in the $s$-to-$t$ path in $T_{c}$ is in a $B$-fragment of
$T-c$, by Lemma B.4, $c\in P(v)$. Thus, $v$ can store the relevant tree-
routing table $R_{T_{c}}(v)$. Essentially, every $v$ has to store such routing
table for every color in $P(v)$. Also, since $c\in P(v)$, $t$ can store in its
label $L(t)$ the tree-routing label $L_{T_{c}}(t)$, and the latter can be
extracted by $s$ and placed on the header of the message at the beginning of
the procedure. Hence, we can simply route the message using Thorup-Zwick
routing scheme of Lemma B.2 on $T_{c}$.

##### Putting It Together.

We now wrap-up the full routing procedure. If $c\notin P(t)$, then $t$ is
connected to $a(t)$, and we get the first case with $a^{*}=a(t)$, which can be
stored in $t$’s label. Thus, suppose $c\in P(t)$. Since
$|P(t)|=O(\mathsf{bp}(G))$, the label of $t$ can store $O(\log n)$ bits for
every color on $P(t)$, and specifically for the color $c$ of interest. If $t$
is in an $A$-fragment in $T-c$, then $t$ can pick an arbitrary $A$-vertex in
its fragment as $a^{*}$, and again we reduce to the first case. Suppose $t$ is
in a $B$-fragment in $T-c$. In this case, $t$ sets $a^{*}$ to be an $A$-vertex
from the nearest $A$-fragment to $t$ in $T_{c}$. The label of $t$ can store
$a^{*}$ and the first recovery edge from $a^{*}$ towards $t$ (i.e.,
$e(a^{*},t,c)$) At the beginning of the procedure, $s$ can find the
information regarding $a^{*}$ and $e(a^{*},t,c)$ in $t$’s label, and write it
on the message header. Now, routing from $s$ to the fragment of $a^{*}$ is by
done by the first case, traversing this fragment towards $e(a^{*},t,c)$ is
done using Thorup-Zwick tree-routing on $T$, and after taking this edge, we
can route the message to $t$ according to the second case.

###  B.3 Construction of Routing Tables and Labels

We now formally define the tables and labels of our scheme, by Algorithms 4, 5
and 6.

Algorithm 4 Creating the table $R(v)$ of vertex $v$

1:store $R_{T}(v)$

2:store port number of the edge from $v$ to its parent in $T$

3:$c(v)\leftarrow\text{color of edge from $v$ to its parent in $T$}$
$\triangleright$ undefined if $v=r$

4:store $c(v)$

5:for each vertex $a\in A$ do

6: store $\mathsf{FirstRecEdge}(v,a,c(v))$

7:for each color $c\in P(v)$ do

8: store $R_{T_{c}}(v)$

Algorithm 5 Creating the label $L(v)$ of vertex $v$

1:store $L_{T}(v)$

2:store $a(v)$, the $A$-endpoint of $P(v)$

3:for each color $c\in P(v)$ do

4: $a(v,c)\leftarrow\text{an $A$-vertex in the nearest $A$-fragment to $v$ in
$T_{c}$}$

5: store $\mathsf{FirstRecEdge}(a(v,c),v,c)$

6: store $L_{T_{c}}(v)$

Algorithm 6 Creating the label $L(c)$ of color $c$

1:for each vertex $a\in A$ do

2: store $\mathsf{FirstRecEdge}(r,a,c)$

##### Size Analysis.

It is easily verified that each store instruction in Algorithms 4, 5 and 6
adds $O(\log n)$ bits of storage. In all of these algorithms, the number of
such instructions is $O(|P(v)|+|A|)$, which is $O(\mathsf{bp}(G))$ by Lemma
B.3. Hence, the total size of any $R(v)$, $L(v)$ or $L(c)$ is
$O(\mathsf{bp}(G)\log n)$ bits.

###  B.4 The Routing Procedure

In the beginning of the procedure, $s$ holds the labels $L(s),L(t)$ and
$L(c)$, and should route the message $M$ to $t$ avoiding the color $c$. As
described in Section B.2, the routing procedure will have two phases. In the
first phase, the message is routed to the fragment of $T-c$ that contains a
carefully chosen vertex $a^{*}\in A$. In the second phase, it is routed from
this fragment to the target $t$.

##### Initialization at $s$.

First, $s$ determines the vertex $a^{*}$ as follows: If $c\in P(t)$, then
$a^{*}=a(t,c)$, which is found in $L(t)$. Otherwise, $a^{*}=a(t)$, the
$A$-endpoint of $P(t)$, which is again found in $L(t)$. Next, $s$ creates the
initial header of the message $M$, that contains:

  * •

The name of the color $c$.

  * •

The name of the vertex $a^{*}$.

  * •

The block $\mathsf{FirstRecEdge}(r,a^{*},c)$, found in $L(c)$.

  * •

The tree-routing label $L_{T}(t)$, found in $L(t)$.

  * •

If $c\in P(t)$, the block $\mathsf{FirstRecEdge}(a^{*},t,c)$ and the tree-
routing label $L_{T_{c}}(t)$, found in $L(T)$.

This information will permanently stay in the header of $M$ throughout the
routing procedure, and we refer to it as the _permanent header_. Verifying
that it requires $O(\log n)$ bits is immediate.

##### First Phase: Routing from $s$ to the Fragment of $a^{*}$.

As in Section B.2, let $e_{1},e_{2},\dots e_{\ell}$ be the recovery edges on
the $s$-to-$a^{*}$ path in $T_{c}$ (according to order of appearance), each
connecting between fragments $X_{i-1}$ and $X_{i}$ of $T-c$. Denote by $v_{i}$
the root of fragment $X_{i}$, and thus $e_{i}=e(v_{i},a^{*},c)$. Recall that
we aim to route the message through these edges and reach the last fragment
$X_{\ell}$, which is an $A$-fragment containing $a^{*}$, according to the
following strategy: Upon reaching a fragment $X_{i}\neq X_{\ell}$, we go up
until we reach its root $v_{i}$, extract information regarding the next
recovery edge $e_{i}$, and use Thorup-Zwick tree-routing on $T$ in order to
get to $e_{i}$. We then traverse it to reach $X_{i+1}$, and repeat the
process.

We now describe this routing procedure formally. The header of $M$ contains
two updating fields:

  * •

$M.\mathsf{UP}$: stores a Boolean value

  * •

$M.\mathsf{NEXT}$: stores a block referring to the next recovery edge in the
path, of the form $\mathsf{FirstRecEdge}(\cdot,a^{*},c)$.

Clearly, this requires $O(\log n)$ bits of storage. We will maintain the
following invariant:

  * (I):

If the message is currently in the fragment $X_{i}\neq X_{\ell}$, and
$M.\mathsf{UP}=0$, then $M.\mathsf{NEXT}$ stores information referring to
$e_{i}$.

At initialization, $s$ sets $M.\mathsf{UP}\leftarrow True$ and
$M.\mathsf{NEXT}\leftarrow\perp$ (a null symbol), which trivially satisfies
the invariant (I). We will use the field $M.\mathsf{UP}$ also to mark that we
are still in the first phase of the routing. During the first phase, it will
be a valid Boolean value. When we reach the fragment $X_{\ell}$, we set
$M.\mathsf{UP}$ to $\perp$ to notify the beginning of the second phase. While
$M.\mathsf{UP}\neq\perp$ (i.e., during the first phase), upon the arrival of
$M$ to a vertex $v$, it executes the code presented in Algorithm 7 to
determine the next hop.

Algorithm 7 First phase: Routing $M$ from $v$ towards the fragment of $a^{*}$
(while $M.\mathsf{UP}\neq\perp$)

1:if $M.\mathsf{UP}=True$ then

2: if $v\neq r$ and $c(v)\neq c$ then

3: send $M$ through the port to $v$’s parent in $T$, found in $R(v)$

4: else

5: find $\mathsf{FirstRecEdge}(v,a^{*},c)$, in permanent header when $v=r$, or
in $R(v)$ when $c(v)=c$

6: $M.\mathsf{NEXT}\leftarrow\mathsf{FirstRecEdge}(v,a^{*},c)$

7: $M.\mathsf{UP}\leftarrow False$

8:if $M.\mathsf{UP}=False$ then

9: $x\leftarrow$ first vertex of the edge $e$ found in $M.\mathsf{NEXT}$

10: if $v\neq x$ then

11: send $M$ in direction of $x$ in $T$, using $L_{T}(x)$ from
$M.\mathsf{NEXT}$, and $R_{T}(v)$ from $R(v)$

12: else$\triangleright$ $v=x$

13: if second vertex of $e$ is in $X_{\ell}$ (as indicated by
$M.\mathsf{NEXT}$) then

14: $M.\mathsf{UP}\leftarrow\perp$ $\triangleright$ will reach $X_{\ell}$ in
next step, and then done

15: else

16: $M.\mathsf{UP}\leftarrow True$

17: send $M$ through the port of the edge $e$ found in $M.\mathsf{NEXT}$

Invariant (I) is maintained when setting $M.\mathsf{UP}\leftarrow False$ in 7,
since we previously set $M.\mathsf{NEXT}$ to $e(v,a^{*},c)$, which is the
first recovery edge in the $v$-to-$a^{*}$ path in $T_{c}$, and thus, when
$v\in X_{i}$, this edge equals $e_{i}$. When the message first reaches a
vertex $s^{\prime}\in X_{\ell}$, the field $M.\mathsf{UP}$ contains a null
value $\perp$, and we start the second phase of the routing procedure, as
described next.

##### Second Phase: Routing from the Fragment of $a^{*}$ to $t$.

Here, we use the careful choice of the vertex $a^{*}$. The easier case is when
$c\notin P(t)$. In this case, $a^{*}=a(v)$, and $t$ is in the same fragment as
$a^{*}$ by Lemma B.4. Therefore, we can use the Thorup-Zwick routing of Lemma
B.2 on $T$ to route the message $M$ from $s^{\prime}$ to $t$. Note that the
label $L_{T}(t)$ is found in the permanent header, and that each intermediate
vertex $v$ on the path has $R_{T}(v)$ in its table.

We now treat the case where $c\in P(t)$. In this case, $a^{*}=a(t,c)$, which
is defined to be an $A$-vertex in the nearest $A$-fragment to $t$ in $T_{c}$,
and hence, $X_{\ell}$ is that nearest $A$-fragment to $t$ in $T_{c}$. Since
$c\in P(t)$, the permanent header stores $\mathsf{FirstRecEdge}(a^{*},t,c)$,
or specifies that the first recovery edge $e(a^{*},t,c)$ is undefined, i.e.
that $a^{*}$ and $t$ are in the same fragment. In the latter case, we can act
exactly as above and route the message over $T$. So, assume
$\mathsf{FirstRecEdge}(a^{*},t,c)$ is found.

Let $x$ and $y$ be the first and second vertices of $e(a^{*},t,c)$. Then
$\mathsf{FirstRecEdge}(a^{*},t,c)$ contains $L_{T}(x)$, so we can route the
message between $s^{\prime},x\in X_{\ell}$ using the Thorup-Zwick routing of
Lemma B.2 on $T$. We then traverse the edge $e(a^{*},t,c)$ from $x$ to $y$,
where the relevant port is stored in the permanent header. We now make the
following important observation:

######  Lemma B.5.

If $v$ is a vertex on the $y$-to-$t$ path in $T_{c}$, then its table $R(v)$
must contain $R_{T_{c}}(v)$.

###### Proof.

First, we note that $v$ must be a $B$-fragment. Indeed, if $v$ were in an
$A$-fragment, then this would be a closer $A$-fragment to $t$ than $X_{\ell}$
in $T_{c}$, which is a contradiction. Therefore, by Lemma B.4, it must be that
$c\in P(v)$. This means that $R_{T_{c}}(v)$ is stored in $R(v)$ by Algorithm
4. ∎

Note that $L_{T_{c}}(t)$ is found in the permanent header, as $c\in P(t)$.
Thus, we can route $M$ from $y$ to $t$ along the connecting path in the
recovery tree $T_{c}$, using the Thorup-Zwick routing of Lemma B.2 on $T_{c}$.
This concludes the routing procedure.

##  Appendix C Single Color Fault: Proof of Theorem 3.5

Labeling. The labeling procedure is presented as Algorithm 8.

Algorithm 8 Labeling for one color fault

1:Colored graph $G$.

2:Labels $L(v)$ for each vertex $v\in V$, and $L(c)$ for each color $c$.

3:$A_{0}\leftarrow\\{a\in V\mid\mathsf{id}(a)=\mathsf{cid}(a,G)\\}$
$\triangleright$ vertices w/ min $\mathsf{id}$ in each connected component of
$G$

4:$A\leftarrow\emptyset$

5:$i\leftarrow 1$

6:while there exists vertex $a_{i}\in V$ with
$\operatorname{dist}_{G}(a_{i},A_{0}\cup A)=i$ do

7: $A\leftarrow A\cup\\{a_{i}\\}$

8: $i\leftarrow i+1$

9:for each vertex $v\in V$ do $\triangleright$ create the label $L(v)$

10: $a(v)\leftarrow$ a closest vertex to $v$ from $A_{0}\cup A$ in $G$

11: $P(v)\leftarrow$ a shortest $v$-to-$a(v)$ path in $G$

12: store in $L(v)$ the id of $a(v)$, $\mathsf{id}(a(v))$

13: store in $L(v)$ a dictionary that maps key $d$ to value
$\mathsf{cid}(v,G-d)$, for every color $d$ on $P(v)$

14:for each color $c$ do $\triangleright$ create the label $L(c)$

15: store in $L(c)$ the name of the color $c$

16: store in $L(c)$ a dictionary that maps key $\mathsf{id}(a)$ to value
$\mathsf{cid}(a,G-c)$, for each $a\in A$

Answering queries. As before, it suffices to show that one can report
$\mathsf{cid}(v,G-c)$ merely from the labels $L(v)$ and $L(c)$. This is done
as follows. If the key $c$ appears in the dictionary of $L(v)$, then
$\mathsf{cid}(v,G-c)$ is the corresponding value, and we are done. Otherwise,
$P(v)$ does not contain the color $c$, so it connects $v$ to $a(v)$ in $G-c$,
and therefore $\mathsf{cid}(v,G-c)=\mathsf{cid}(a(v),G-c)$. Recall that
$a(v)\in A_{0}\cup A$. If the key $\mathsf{id}(a(v))$ appears in the
dictionary of $L(c)$, then $\mathsf{cid}(a(v),G-c)$ is the corresponding
value, and we are done. Otherwise, it must be that $a(v)\in A_{0}$. Recall
that $A_{0}$ contains vertices having minimum $\mathsf{id}$ in their connected
component in $G$. This implies that
$\mathsf{cid}(a(v),G-c)=\mathsf{id}(a(v))$, and the latter is stored in
$L(v)$.

Length analysis. Let $k$ be the halting iteration of the while loop in
Algorithm 8 (line 4). Then $|A|=k-1$, so the length of each color label is
$O(k\log n)$ bits. Also, by the while condition, each vertex $v\in V$ has
distance less than $k$ from $A_{0}\cup A$ in $G$, so $P(v)$ contains less than
$k$ edges, hence also less than $k$ colors. Therefore, the length of $L(v)$ is
also $O(k\log n)$ bits.

We now prove that $k=O(\mathsf{bp}(G))$. Let $A^{\prime}=\\{a_{i}\mid
i\geq\lceil k/2\rceil\\}$ be the “second half” of chosen $A$-vertices. Note
that $|A^{\prime}|\geq k/2$. For each $i=1,\dots k-1$, denote by $A_{i}$ the
state of set $A$ right after the $i$-th iteration. If $a_{i},a_{j}\in
A^{\prime}$ with $i>j$, then $a_{j}\in A_{i-1}$, hence

$\operatorname{dist}_{G}(a_{i},a_{j})\geq\operatorname{dist}_{G}(a_{i},A_{0}\cup
A_{i-1})=i>\lceil k/2\rceil.$

Therefore, $B(a_{i},\lfloor k/4\rfloor)$ and $B(a_{j},\lfloor k/4\rfloor)$ are
disjoint. Also, if $a_{i}\in A^{\prime}$, then
$\operatorname{dist}_{G}(a_{i},A_{0}\cup A)=i>\lfloor k/4\rfloor$, so 3.2
implies that $B(a_{i},\lfloor k/4\rfloor)$ is proper. Thus, the collection of
$\lfloor k/4\rfloor$-balls centered at the $A^{\prime}$ vertices certifies
that $\lfloor k/4\rfloor\leq\mathsf{bp}(G)$, which concludes the proof.

######  Remark.

The proof extends seamlessly to vertex-colored graphs. It is worth noting that
if the vertex $a(v)$ has the color $c$, then $\mathsf{cid}(v,G-c)$ is stored
in $L(v)$ (since $a(v)\in P(v)$).

##  Appendix D Nearest Colored Ancestor Labels

In this section, we show how the $O(n)$-space, $O(\log\log n)$-query time
nearest colored ancestor data structure of [GLMW18] can be used to obtain
$O(\sqrt{n}\log n)$-bit labels for this problem.

The labels version of nearest colored ancestor is formally defined as follows.
Given a rooted $n$-vertex forest $T$ with colored vertices, where each vertex
$v$ has an arbitrary unique $O(\log n)$-bit identifier $\mathsf{id}(v)$, the
goal is to assign short labels to each vertex and color in $T$, so that the
$\mathsf{id}$ of the nearest $c$-colored ancestor of vertex $v$ can be
reported by inspecting the labels of $c$ and $v$. The reduction from the
centralized setting implies that such a labeling scheme can be used ‘as is’
for connectivity under one color fault.101010 When constructing the nearest
colored ancestor labels in the reduction, we augment the $\mathsf{id}$ of each
vertex $v$ with $\mathsf{cid}(v,G-c)$, where $c$ is the color of the tree edge
from $v$ to its parent.  First, by Theorem 3.6, we get:

######  Corollary D.1.

Every labeling scheme for nearest colored ancestor in $n$-vertex forests must
have label length $\Omega(\sqrt{n})$ bits. Furthermore, this holds even for
paths, as their ball-packing number is $\Omega(\sqrt{n})$.

######  Remark.

The above lower bound can be strengthened to $\Omega(\sqrt{n}\log n)$. This is
by considering the problem that our scheme _actually_ solves: report the
minimum $\mathsf{id}$ of a vertex connected to $v$ in $G-c$, from the labels
of $v$ and $c$. For this problem, one can extend the proof of Theorem 3.6 to
show an $\Omega(\sqrt{n}\log n)$-bit lower bound for paths. The reduction
described above shows that a nearest colored ancestor labeling scheme can be
used to report such minimum $\mathsf{id}$s.

The data structure in [GLMW18] can, in fact, be transformed into
$O(\sqrt{n}\log n)$-bit labels. We first briefly explain how this data
structure works. Each vertex $v$ gets two _time-stamps_
$\mathsf{pre}(v),\mathsf{post}(v)$, which are the first and last times a DFS
traversal in $T$ reaches $v$. The time-stamps of $c$-colored vertices are
inserted to a _predecessor structure_ [vEBKZ77, Wil83] for color $c$. For each
time-stamp of a ($c$-colored) vertex $u$, we also store the $\mathsf{id}$ of
the nearest $c$-colored (strict) ancestor of $u$. A query $(v,c)$ is answered
by finding the predecessor of $\mathsf{pre}(v)$ in the structure of $c$. If
the result is $\mathsf{pre}(u)$, then $u$ is returned. If it is
$\mathsf{post}(u)$, then the ancestor pointed by $u$ is returned. Correctness
follows by standard properties of DFS time-stamps. The predecessor structure
for $c$ answers queries in $O(\log\log n)$ time, and takes up $O(|V_{c}|)$
space (in words), where $V_{c}$ is the set of $c$-colored vertices. The total
space is $O(\sum_{c}|V_{c}|)=O(n)$.

To construct the labels, let $\mathcal{H}=\\{c\mid|V_{c}|\geq\sqrt{n}\\}$ be
the _highly prevalent_ colors, and $\mathcal{R}$ be the rest of the colors. As
there are only $n$ vertices, $|\mathcal{H}|=O(\sqrt{n})$. We can therefore
afford to let each vertex $v$ explicitly store in its label the $\mathsf{id}$
of its nearest $c$-color ancestor, for each $c\in\mathcal{H}$. To handle the
remaining $\mathcal{R}$-colors, we store in the label of each
$c\in\mathcal{R}$ the predecessor structure for $c$, which only requires
$O(|V_{c}|\log n)=O(\sqrt{n}\log n)$ bits. By augmenting the vertex labels
with $\mathsf{pre}(\cdot)$ times (requiring only $O(\log n)$ additional bits),
we can also answer queries with colors in $\mathcal{R}$. We obtain:

######  Corollary D.2.

There is a labeling scheme for nearest colored ancestor in $n$-vertex forests,
with labels of length $O(\sqrt{n}\log n)$ bits. Queries are answered in
$O(\log\log n)$ time.

##  Appendix E Limitations of the Lower Bound Technique of Theorem 4.6

The ‘technique’ in the proof of Theorem 4.6 is devising a protocol for
$\textsc{Index}(N)$ that uses, _as a black-box_ , a labeling scheme for
$n$-vertex graphs, by specifying:

  1. 1.

A (‘worst-case’) graph topology $G$, known in advance to Alice and Bob.

  2. 2.

A coloring procedure by which Alice colors her copy of $G$ according to her
input.

  3. 3.

Which labels are sent from Alice to Bob.

  4. 4.

A recovery procedure of Bob, using the received labels for connectivity
queries.

Let $S$ be the maximum possible number of labels that Alice sends in an
execution of the communication protocol. We assume that $N=\Theta(n)$, and
justify this assumption later. Then, Lemma 2.1 yields a lower bound of
$\Omega(n/S)$ on the label length, and we now argue why this lower bound
cannot be stronger than $\tilde{\Omega}(n^{1-1/(f+1)})$.

Let $C$ be the maximum possible number of _color labels_ that Alice sends. Bob
can only simulate the failure of color for which he has a label. So, any color
whose label is not sent can be considered non-faulty, and replaced with
$\perp$ in the coloring procedure, without affecting the correctness of the
protocol.

Consider the simple labeling scheme where each vertex label $L(v)$ stores
$\mathsf{cid}(v,G-F)$ for every set $F$ of at most $f$ colors, and a color
label simply stores the color’s name. As there are $C$ colors, the maximum
length of a label given by this scheme is $O(C^{f}\log n)$ bits. Applying the
lower bound, we get $\Omega(n/S)=C^{f}\log n\leq S^{f}\log n$, hence
$S=\tilde{\Omega}(n^{1/(f+1)})$, and thus $n/S=\tilde{O}(n^{1-1/(f+1)})$,
which concludes this argument.

One could hope to encode more than $N=\Theta(n)$ bits using the topology $G$,
as the number of bits to encode a specific coloring of $G$ is $\Theta(m\log
C)$. However, the sparsification of Theorem 4.2 show that the colored $G$ has
a subgraph $H$ (which depends on the coloring) with $\tilde{O}(n)$ edges,
where all connectivity queries give the same answers in $H$ as in $G$. As
Bob’s recovery procedure only uses such queries, the information he recovers
can be encoded by this colored subgraph $H$, and hence contains at most
$\tilde{\Theta}(n)$ bits.

##  Appendix F Hitting Set

The following lemma is well known. The proof, adapted from [ACIM99], is based
on the equivalence of the hitting set and set cover problems.

######  Lemma F.1 (Deterministic Hitting Set).

Let $V$ be a set of size $n$, and let $S_{1},\dots,S_{k}\subseteq V$, each of
size at least $\Delta$. Then there is a subset $U\subseteq V$ with
$|U|=O((n/\Delta)\log k)$ such that $S_{i}\cap U\neq\emptyset$ for all
$i\in\\{1,\dots,k\\}$. The set $U$ can be found by an efficient deterministic
algorithm.

###### Proof.

For every $v\in V$, let $A_{v}=\\{i\mid v\in S_{i}\\}$, and consider the set
cover instance $\mathcal{A}=\\{A_{v}\mid v\in V\\}$. Take $U$ such that
$\\{A_{u}\mid u\in U\\}$ is the cover produced by the greedy algorithm for
$\mathcal{A}$. To spell this out: Initialize $U=\emptyset$. While there is $i$
with $S_{i}\cap U=\emptyset$ (i.e., $i\notin\bigcup_{v\in U}A_{v}$), choose
$u\in V$ that maximizes the quantity $|A_{u}-\bigcup_{v\in U}A_{v}|=|\\{i\mid
u\in S_{i},S_{i}\cap U=\emptyset\\}|,$ and update $U\leftarrow U\cup\\{u\\}$.
This can be implemented in linear time (in the input size) using a bucket
queue.

It is known that the greedy solution for set cover approximates the optimal
_fractional_ solution within a $O(\log k)$ factor [Joh74, Lov75]. Give weight
$w(A_{v})=1/\Delta$ to each set $A_{v}$. This is a feasible fractional
solution, as for every $i\in\\{1,\dots,k\\}$, $\sum_{v:i\in
A_{v}}w(A_{v})=|S_{i}|/\Delta\geq 1.$ Its value is $\sum_{v\in
V}w(A_{v})=n/\Delta$. Thus, $|U|=O((n/\Delta)\cdot\log k)$. ∎