# Color Fault-Tolerant Spanners

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

We initiate the study of spanners in arbitrarily vertex- or edge-colored
graphs (with no “legality” restrictions), that are resilient to failures of
_entire color classes_. When a color fails, all vertices/edges of that color
crash. An $f$-color fault-tolerant ($f$-CFT) $t$-spanner of an $n$-vertex
colored graph $G$ is a subgraph $H$ that preserves distances up to factor $t$,
even in the presence of at most $f$ color faults. This notion generalizes the
well-studied $f$-vertex/edge fault-tolerant ($f$-V/EFT) spanners. The size of
an $f$-V/EFT spanner crucially depends on the number $f$ of vertex/edge faults
to be tolerated. In the colored variants, even a single color fault can
correspond to an unbounded number of vertex/edge faults.

The key conceptual contribution of this work is in showing that the size
(number of edges) required by an $f$-CFT spanner is in fact comparable to its
uncolored counterpart, with no dependency on the size of color classes. We
provide optimal bounds on the size required by $f$-CFT $(2k-1)$-spanners, as
follows:

  * •

When vertices have colors, we show an upper bound of $O(f^{1-1/k}n^{1+1/k})$
edges. This precisely matches the (tight) bounds for $(2k-1)$-spanners
resilient to $f$ _individual_ vertex faults [Bodwin et al., SODA 2018; Bodwin
and Patel, PODC 2019].

  * •

For colored edges, we show that $O(fn^{1+1/k})$ edges are always sufficient.
Further, we prove this is tight, i.e., we provide an $\Omega(fn^{1+1/k})$
(worst-case) lower bound. The state-of-the-art bounds known for the
corresponding uncolored setting of edge faults are (roughly)
$\Theta(f^{1/2}n^{1+1/k})$ [Bodwin et al., SODA 2018; Bodwin, Dinitz and
Robelle, SODA 2022].

  * •

We also consider a _mixed_ model where both vertices and edges are colored. In
this case, we show tight $\Theta(f^{2-1/k}n^{1+1/k})$ bounds.

Thus, CFT spanners exhibit an interesting phenomenon: while (individual) edge
faults are “easier” than vertex faults, edge-color faults are “harder” than
vertex-color faults.

Our upper bounds are based on a generalization of the blocking set technique
of [Bodwin and Patel, PODC 2019] for analyzing the (exponential-time) greedy
algorithm for FT spanners. We complement them by providing _efficient_
constructions of CFT spanners with similar size guarantees, based on the
algorithm of [Dinitz and Robelle, PODC 2020].

##  1 Introduction

Let $G$ be an $n$-vertex weighted graph. A _spanner_ of $G$ is a subgraph that
approximately preserves distances. Formally, a subgraph $H$ is a $t$-spanner
of $G$ if $\operatorname{dist}_{H}(u,v)\leq
t\cdot\operatorname{dist}_{G}(u,v)$ for all $u,v\in V$ (where
$\operatorname{dist}_{X}$ denotes the shortest path distance in a graph $X$).
Since their introduction by Peleg and Ullman [PU88] and Peleg and Schäffer
[PS89], spanners have been found to be extremely useful for a wide variety of
applications, including network tasks like routing and synchronization [PU89,
TZ01, Cow01, CW04, PU88], distance estimation [TZ05, BS04], preconditioning
linear systems [EEST08], and many others.

In real-world scenarios, spanners are frequently employed in systems whose
components are susceptible to occasional breakdowns. It is therefore desirable
to have spanners possessing resilience to such failures, leading to the notion
of _fault-tolerant (FT) spanners_. Two extensively studied types of faults are
_edge faults_ and _vertex faults_. Spanners in the edge/vertex fault-tolerant
(E/VFT) settings are defined as follows:

######  Definition 1.1 (E/VFT Spanner).

An $f$-EFT (VFT) $t$-spanner of $G$ is a subgraph $H$ such that for every set
$F$ of at most $f$ edges (vertices) in $G$, it holds that $H-F$ is a
$t$-spanner of $G-F$.

E/VFT spanners have received major interest in recent years; see, e.g.,
[CLPR10, DK11, BDPW18, BP19, DR20, BDR21, BDR22, Par22] and references
therein.

In this work, we introduce and study _color fault tolerant_ models. The
framework is the following: the edges or vertices are arbitrarily partitioned
into classes, or equivalently, associated with colors, and $f$ such _color
classes_ might fail. Each of the E/VFT settings gets a colored counterpart
setting, denoted E/VCFT (the C stands for ‘color’). The standard E/VFT
settings are obtained as special cases, by giving each edge/vertex a different
color.

Faulty color classes have been used to model Shared Risk Resource Groups
(SRRG), which arise in many practical contexts such as optical
telecommunication networks and multi-layered networks; see [CDP+07, Kui12,
ZCTZ11] and references therein for a detailed discussion. Previous work in
this context mainly focused on colored variants of classical graph problems
(and their hardness). A notable such problem is _diverse routing_ , where the
goal is to determine if two (or more) color disjoint paths between two
vertices [Hu03, EBR+03, MN02] exist (and if so, finding them). In such
algorithmic contexts, replacing a dense colored graph by a sparse CFT spanner
could potentially help to improve algorithmic performance, similarly to V/EFT
spanners for uncolored graphs.

##### Sparse Connectivity Certificates.

Connectivity certificates are subgraph notions that are closely related to FT
spanners. Intuitively, a _$\lambda$ -edge (or $\lambda$-vertex) connectivity
certificate_ serves as concise “proof” to establish the $\lambda$-edge/vertex
connectivity of a graph $G$. Formally, it is a subgraph $H$ of $G$ such that
every two vertices $u,v$ are $\lambda$-edge/vertex connected in $G$ if and
only if they are $\lambda$-edge/vertex connected in $H$. The concept of
connectivity certificates was presented by Nagamochi and Ibaraki [NI92], who
showed the existence of $\lambda$-connectivity certificates with at most
$\lambda(n-1)$ edges for every $n$-vertex graph. These play a crucial role in
various graph algorithms [Mat93, CKT93, KM97, GK13, FNY+20, LNP+21]. Every
$\lambda$-V/EFT $(2k-1)$-spanner, for every $1\leq k<\infty$, is _by
definition_ also a $\lambda$ connectivity certificate, as observed e.g. in
[Par19, Par22]. Such a spanner with $O(\lambda^{1-1/k}n^{1+1/k})$ edges always
exists [BP19], so choosing $k=\Theta(\log n)$ yields sparse
$\lambda$-connectivity certificates of $O(\lambda n)$ size.

Due to the min-cut max-flow theorem, edge/vertex-connectivity can be defined
equivalently using cuts and flows. In the colored case, this relationship no
longer holds: the minimum set of colors whose removal disconnects two vertices
can be arbitrarily larger than the maximum number of color-disjoint paths
connecting them [CDP+07]. Hence, “color-connectivity certificates” may take
two different meanings for cuts and flows. CFT Spanners can then be seen as
color-connectivity certificates _in the cut sense_. To avoid confusion, we
call the latter $\lambda$-CFT-connectivity certificates. Similarly to their
uncolored counterparts, such CFT-connectivity certificates may provide useful
tools when dealing with colored graphs. As this work focuses on the stronger
notion of CFT spanners, (wort-case) optimal results on the size of CFT-
connectivity certificates are implied as direct corollaries.

##### A Mixed Setting.

We additionally consider another possible setting, which we call _mixed_ ,
that allows for both edge faults and vertex faults. That is, in the uncolored
setting, the faulty-set $F$ is a subset of $V(G)\cup E(G)$ of size $\leq f$.
In the colored setting, both edges and vertices have colors (and a color may
appear on both vertices and edges). We use the shorthand MFT for the uncolored
mixed setting, and MCFT for its colored counterpart. To the best of our
knowledge, MFT spanners have not been explicitly defined, but many known
results for the E/VFT settings implicitly apply to them.

###  1.1 Our Contribution

We initiate the study of FT spanners supporting $f$ color faults in colored
graphs. A naïve approach for handling color faults is to treat them as many
edge/vertex faults. If each color class contains at most $\Delta$
edges/vertices, then a $\Delta f$-FT spanner for edge/vertex faults is clearly
an $f$-CFT spanner. While this solution might be plausible for small $\Delta$,
it is useless for large $\Delta$. As the coloring is arbitrary, it may even be
that $\Delta=\Omega(n)$. Thus, the resulting spanner from this naïve approach
might have $\Omega(n^{2})$ edges even when $f=1$, i.e., when only a single
color fault may occur. Conceptually, the main contribution of our work is
showing that in the realm of FT spanners, one can handle $f$ color faults
almost as efficiently as $f$ _individual_ edge/vertex faults, without any
dependence on $\Delta$.

Our main results regarding CFT spanners are:

######  Theorem 1.2.

For every $k,f\geq 1$, and every colored $n$-vertex graph $G$, there exists an
$f$-CFT $(2k-1)$-spanner with the following size bounds:

  1. 1.

$O(fn^{1+1/k})$ edges in the edge-colored setting,

  2. 2.

$O(f^{1-1/k}n^{1+1/k})$ edges in the vertex-colored setting, and

  3. 3.

$O(f^{2-1/k}n^{1+1/k})$ edges in the mixed setting of both edge and vertex
colors.

Moreover, the above bounds are tight assuming the Erdős Girth Conjecture.

Table 1 presents the known bounds for non-colored FT-spanners, compared to the
color settings. The bounds of Theorem 1.2 are based on the _exponential-time_
FT greedy algorithm. We further provide polynomial-time constructions of CFT
spanners with nearly optimal size guarantees (up to $\operatorname{poly}(k)$
factors). We obtain $\lambda$-CFT connectivity certificates as immediate
corollaries:

######  Theorem 1.3.

Every colored $n$-vertex graph $G$ has a subgraph $H$ such that, for every two
vertices $u,v$, and every set $C$ of at most $\lambda$ colors, $u,v$ are
connected in $H-C$ iff they are connected in $G-C$, where $|E(H)|=O(\lambda
n)$ if the graph has either colored edges or colored vertices (but not both),
and $|E(H)|=O(\lambda^{2}n)$ when both vertices and edges are colored. This is
(worst-case) optimal.

Setting | Upper bound | Ref. | Lower bound | Ref.
---|---|---|---|---
EFT |  |  $O_{k}(f^{\tfrac{1}{2}-\tfrac{1}{2k}}\cdot n^{1+\tfrac{1}{k}}+fn)$, odd $k$
---
$O_{k}(f^{\tfrac{1}{2}}\cdot n^{1+\tfrac{1}{k}}+fn)$, even $k$
[BDR22] | $\Omega(f^{\tfrac{1}{2}-\tfrac{1}{2k}}\cdot n^{1+\tfrac{1}{k}}+fn)$ | [BDPW18]
ECFT | $O(f\cdot n^{1+\tfrac{1}{k}})$ | New | $\Omega(f\cdot n^{1+\tfrac{1}{k}})$ | New
VFT | $O(f^{1-\tfrac{1}{k}}\cdot n^{1+\tfrac{1}{k}})$ | [BP19] | $\Omega(f^{1-\tfrac{1}{k}}\cdot n^{1+\tfrac{1}{k}})$ | [BDPW18]
VCFT | New
MFT | $O(f^{1-\tfrac{1}{k}}\cdot n^{1+\tfrac{1}{k}})$ | [BP19] | $\Omega(f^{1-\tfrac{1}{k}}\cdot n^{1+\tfrac{1}{k}})$ | [BDPW18]
MCFT | $O(f^{2-\tfrac{1}{k}}\cdot n^{1+\tfrac{1}{k}})$ | New | $\Omega(f^{2-\tfrac{1}{k}}\cdot n^{1+\tfrac{1}{k}})$ | New

Table 1: Bounds on the worst-case size required by $f$-FT $(2k-1)$-spanners.
All lower bounds are conditioned on the Erdős Girth Conjecture [Erd63]. The
lower bounds in the ECFT and MCFT settings cannot exceed $\Omega(n^{2})$ for
simple graphs, but we omit the $\min\\{\cdot,n^{2}\\}$ expression for ease of
reading. The bounds in the MFT settings are implicit by the cited works.

##### On FT Spanners for Multi-Graphs.

Interestingly, the bounds we provide for _simple_ colored graphs match the
bounds required by E/V/MFT spanners for uncolored _multi-graphs_. All of our
results apply both to simple and multi-graphs. This is in contrast to the
uncolored setting, where “multi” FT-spanners are denser than “simple” ones.
See discussion in Appendix A.

##### Color Lists.

Consider the following generalization of the color-faults model: Instead of
having a single color per vertex/edge, each of them now has a _list_ of colors
to which it is sensitive. That is, the failure of any single color from the
list makes the vertex/edge crash. Notice that each of the E/V/MCFT setting is
obtained as a special case by restricting the sizes of the lists; e.g., the
ECFT setting is obtained by restricting edges to have lists of length 1, and
the vertices to have empty 0-length lists. In fact, this generalized setting
is also considered in the context of Shared Risk Resource Groups (SRRG); see
[CDP+07] and references therein. By studying this variant, we obtain the
following generalization of Theorem 1.2:

######  Theorem 1.4.

Fix constant integers $\mu,\nu\geq 0$. Let $G$ be an $n$-vertex graph, where
each edge (resp., vertex) has a list of at most $\mu$ (resp., $\nu$) colors,
such that the failure of _any_ color in the list makes the edge (resp.,
vertex) fail. Then, there exist an $f$-CFT $(2k-1)$-spanner with
$O(f^{\mu+\nu(1-1/k)}n^{1+1/k})$ edges. Moreover, this is tight assuming the
Erdős Girth Conjecture.

The bounds of Theorem 1.2 are obtained by taking $\mu,\nu\in\\{0,1\\}$. The
proof is a relatively straightforward extension of the proofs for the E/V/MCFT
settings, using inductive arguments; it is given in Appendix B.

###  1.2 Technical Overview

##### Upper bounds (Section 3).

To prove size upper bounds for CFT spanners, we build upon the powerful yet
strikingly simple _blocking set_ technique of Bodwin and Patel [BP19]. This is
a method for analyzing the spanner $H$ given by the (exponential-time) _FT
greedy algorithm_ , used in [BP19] to obtain optimal bounds in the VFT
setting. For clarity of exposition, we focus our discussion here only on the
corresponding vertex-colored setting.

Bodwin and Patel define a blocking set as a collection of edge-vertex pairs,
such that each short ($\leq 2k$) cycle in $H$ contains one of the pairs. On an
intuitive level, a graph that admits a small blocking set is close to having
high girth, forcing it to be sparse. The FT greedy algorithm naturally induces
a blocking set of size $f|E(H)|$, which ultimately yields the upper bound on
the size of $H$ (as explained next). The trivial adaption of this algorithm to
the CFT settings then leads to the “right” extension of a blocking set: a
collection of edge-color pairs such that for every short cycle $\Sigma$, at
least one pair has both its edge and its color appearing on $\Sigma$.

The analysis of $|E(H)|$ is by considering a random subgraph of $H$ induced on
a fraction of $\approx 1/f$ vertices, and removing the edges of surviving
blocking-set-pairs. The resulting subgraph, denoted $\hat{H}_{S}$, has
$O(n/f)$ vertices and large girth, and therefore $O((n/f)^{1+1/k})$ edges
according to the folkore _Moore Bounds_. On the other hand, direct
calculations show that $\Omega(|E(H)|/f^{2})$ edges are expected to survive,
hence $|E(H)|=O(f^{1-1/k}n^{1+1/k})$. Again, there seems to be a natural
adaptation for (vertex) colors: sample a random fraction of $\approx 1/f$
_color classes_. The problem that arises is that even though $\hat{H}_{S}$ has
$O(n/f)$ vertices _in expectation_ , it is quite probable to have $\Omega(n)$
vertices (say, if a color class of size $\Omega(n)$ is sampled). More
conceptually, the problem is that vertices cannot be sampled independently,
preventing us from using concentration bounds. Naïvely carrying out the same
analysis with a trivial $O(n)$ bound on the number of sampled vertices yields
only an $O(f^{2}n^{1+1/k})$ bound on the size of the spanner $H$.

We show that even in the independence-deprived circumstances of the VCFT
setting, the same bounds of the VFT setting can be obtained. Our analysis is
carefully designed to harness the little independence we do have, between
different color classes. It has three main ingredients.

  * (1)

We first show that effectively, we may assume that greedy spanner $H$ is
_color-bipartite_ : a bipartite graph where each color class is fully
contained in one of the sides.

  * (2)

To complement this, we use a “symmetric” version of the Moore Bounds: a
bipartite graph with sides $L,R$ and girth $>2k$ has
$O(|L||R|^{1/k}+|R||L|^{1/k})$ edges.111Stronger bipartite Moore Bounds exist
[Hoo02], but this weaker bound suffices for our needs.

  * (3)

Combining the independence between the color classes _from different sides_
with the Moore Bounds, we show that the random graph $\hat{H}_{S}$ has
$O((n/f)^{1+1/k})$ edges in expectation.

##### Lower bounds (Section 4).

Our lower bounds, as most spanner lower bounds, are conditioned on the famous
and widely believed Erdős Girth Conjecture [Erd63], implying the existence of
an $n$-vertex graph $G_{ER}$ with $\Omega(n^{1+1/k})$ edges that has no proper
subgraph as a $(2k-1)$-spanner.

For edge-colored graphs, our strategy is to pack $f$ copies of an $n$-vertex
Erdős graph $G_{ER}$, denoted $G_{1},\dots,G_{f}$, on the same set of
vertices, with little overlap. We then consider the union graph
$\bigcup_{i}G_{i}$ (ignoring overlaps), where each edge originating from
$G_{i}$ is given the color $i$. This graph has $\Omega(fn^{1+1/k})$ edges, and
no proper $f$-ECFT $(2k-1)$-spanner.

In the mixed-colored setting, we “encode” $f^{2}$ disjoint $f$-ECFT lower
bound instances in a graph with $fn$ properly colored vertices, such that each
instance can be isolated by failing $2f$ vertex-colors. Thus, this graph has
no proper $3f$-MCFT spanner.

##### Efficient algorithms (Section 5).

We show efficient CFT spanner constructions based on the technique of Dinitz
and Robelle [DR20]. Their approach was to modify the greedy algorithm in the
E/VFT settings to have polynomial running time, while ensuring it still
induces a small blocking set, only larger by an $O(k)$ factor than that of the
“vanilla” FT greedy algorithm. Thus, the size analysis based on blocking sets
still applies. Our (existential) upper bounds generalize this last component
to colored settings. We then augment the [DR20] algorithm to produce small
_colored_ blocking sets, and thus achieve efficient constructions.

##### Remark on Optimality Beyond the Girth Conjecture.

Let $\gamma(n,2k)$ denote the maximum number of edges in an $n$-vertex graph
of girth $>2k$. The Moore Bounds show that $\gamma(n,2k)=O(n^{1+1/k})$, and
Erdős’ Girth Conjecture is that this is tight up to a constant factor. Our
lower bounds can be formulated purely in terms of the $\gamma$ function:
$\Omega(f\cdot\gamma(n,2k))$ edges in the ECFT setting,
$\Omega(f^{2}\cdot\gamma(n/f,2k))$ edges in VCFT setting, and
$\Omega(f^{3}\cdot\gamma(n/f,2k))$ edges in MCFT setting. As for the upper
bounds: In the ECFT case, the upper bound matches the lower bound also in
terms of $\gamma$. In the VCFT and MCFT settings, the upper bounds are
matching assuming only much weaker conditions on $\gamma$ than the Girth
Conjecture; it is enough to assume that
$\gamma(n,2k)=\Theta(n\cdot\beta(n,2k))$, where $\beta(\cdot,2k)$ is _concave_
(the Girth Conjecture is that $\beta(n,2k)=n^{1/k}$).

##  2 Preliminaries: A Unified FT Framework

We now present a unified formal framework for all six E/V/M(C)FT settings, to
help avoid tedious repetitions later on.

Henceforth, assume every edge/vertex $x\in E(G)\cup V(G)$ is associated with a
color $c(x)\in\mathcal{C}$, where $\mathcal{C}$ is some finite set called the
_color palette_. The coloring is arbitrary, and there are no “legality”
restrictions. For example, two neighboring vertices may share the same color.
It is also allowed that the same color appears both on edges and on vertices.
For $c\in\mathcal{C}$, we denote the sets of $c$-colored edges and vertices by
$E_{c}(G)=\\{e\in E(G)\mid c(e)=c\\}$ and $V_{c}(G)=\\{v\in V(G)\mid
c(v)=c\\}$. The edges of $G$ are weighted, where $w(e)=w(u,v)$ denotes the
weight of edge $e=\\{u,v\\}$.

The _fault universe_ $\mathcal{F}$ is defined separately for each of the
fault-tolerant settings:

Setting | EFT | VFT | MFT | ECFT | VCFT | MCFT
---|---|---|---|---|---|---
$\mathcal{F}=$ | $E(G)$ | $V(G)$ | $E(G)\cup V(G)$ | $\\{E_{c}(G)\\}_{c\in\mathcal{C}}$ | $\\{V_{c}(G)\\}_{c\in\mathcal{C}}$ | $\\{E_{c}(G)\cup V_{c}(G)\\}_{c\in\mathcal{C}}$

We say that an edge $e=\\{u,v\\}\in E(G)$ is _damaged_ by $x\in\mathcal{F}$ if
the failure of $x$ causes $e$ to fail. Formally, $x$ damages $e$ if: $x=e$ in
EFT, $x\in\\{u,v\\}$ in VFT, $x\in\\{e,u,v\\}$ in MFT, $e\in x$ in ECFT,
$\\{u,v\\}\cap x\neq\emptyset$ in VCFT, and $\\{e,u,v\\}\cap x\neq\emptyset$
in MCFT. Note that in the colored settings, there is a one-to-one
correspondence between the fault universe $\mathcal{F}$ and the set of colors
$\mathcal{C}$. So, when $S\subseteq\mathcal{F}$, we say that $S$ contains the
color $c$, and abuse notation by writing $c\in S$, when $S$ contains the
element corresponding to $c$ from the fault universe $\mathcal{F}$ (which
depends on the setting). We denote by $G-S$ the subgraph of $G$ obtained by
deleting all edges damaged by some $x\in S$, and by $G[S]\coloneqq
G-(\mathcal{F}-S)$, which is the subgraph obtained by keeping all edges that
can only be damaged by faults from $S$.

We now formally state the general FT spanner definition, applying to all
settings:

######  Definition 2.1 (General FT Spanner).

An $f$-FT $t$-spanner of $G$ with respect to a fault universe $\mathcal{F}$
(defined by the given setting) is a subgraph $H$ such that for every
$F\subseteq\mathcal{F}$ with $|F|\leq f$, it holds that $H-F$ is a $t$-spanner
of $G-F$.

##  3 Upper Bounds

The FT variant of the greedy spanner algorithm of Alth’́ofer et al. [ADD+93],
presented as Algorithm 1, has been central in the study of spanners in
general, and FT spanners in particular.

Algorithm 1 $\mathsf{FTGreedySpanner}(G,k,f)$

1:$H\leftarrow(V(G),\emptyset)$

2:for each $e=\\{u,v\\}\in E(G)$ in increasing order of weight do

3: if there is $F\subseteq\mathcal{F}$, $|F|\leq f$, not damaging $e$, such
that $\operatorname{dist}_{H-F}(u,v)>(2k-1)w(e)$ then

4: $H\leftarrow H\cup\\{e\\}$

5:return $H$

Aside from its immediate correctness, the greedy approach has been proven to
produce strong and often optimal upper bounds on the (worst-case) size of
E/VFT spanners (e.g., see [BP19, BDR22]), making it an “immediate suspect” to
investigate for getting upper bounds on the size of CFT spanners as well. The
major downside of the naïve FT greedy algorithm is its exponential-in-$f$
running time, which makes it intractable for many algorithmic applications.
However, it is often the case that modified polynomial-time greedy approaches
(with suitably modified analysis) can be devised to produce very close size
bounds [BDR21, DR20].

In this section, we provide existential size bounds on CFT spanners via the
naive FT greedy algorithm, using the _blocking set_ technique of Bodwin and
Patel [BP19]. We show:

######  Theorem 3.1.

The number of edges $m$ in the graph $H$ constructed by the FT greedy
algorithm (Algorithm 1) can be bounded as follows:

  1. 1.

In the ECFT setting, $m=O(fn^{1+1/k})$.

  2. 2.

In the VCFT setting, $m=O(f^{1-1/k}n^{1+1/k})$.

  3. 3.

In the MCFT setting, $m=O(f^{2-1/k}n^{1+1/k})$

###  3.1 Blocking Sets and Random Blocked Subgraphs

Denote by $H$ the output of Algorithm 1, and by $m$ its number of edges. The
size analysis of $H$ hinges on a generalized definition of blocking sets,
capturing all six E/V/M(C)FT settings.

######  Definition 3.2 (Blocking Set).

A $2k$-_blocking set_ of $H$ is a subset $B\subseteq E(H)\times\mathcal{F}$
that sastifies the following conditions:

  1. (i)

If $(e,x)\in B$, then $e$ is not damaged by $x$.

  2. (ii)

For every cycle $\Sigma$ in $H$ on $\leq 2k$ edges, there exist $(e,x)\in B$
such that $e\in\Sigma$, and some (other) edge of $\Sigma$ is damaged by $x$.
Abusing notation, we denote this condition by $(e,x)\in B\cap\Sigma$.

The same arguments as in [BP19] imply the existence of small blocking set for
$H$:

######  Lemma 3.3 (Modification of [BP19, Lemma 3]).

There is a $2k$-blocking set $B$ of $H$ such that $|B|\leq fm$. Moreover, for
every edge $e\in E(H)$, there are at most $f$ pairs of the form $(e,x)$ in
$B$.

###### Proof.

For every $e=\\{u,v\\}\in E(H)$, let $F_{e}\subseteq\mathcal{F}$, $|F_{e}|\leq
f$ be the set of faults not damaging $e$ that caused $e$’s insertion. I.e., at
the time $e$ was considered by Algorithm 1, it was the case that
$\operatorname{dist}_{H-F_{e}}(u,v)>(2k-1)w(e)$. Define

$B=\\{(e,x)\mid e\in E(H),x\in F_{e}\\}.$

Every edge $e\in E(H)$ participates in at most $f$ pairs $(e,x)\in B$, and
condition (i) of Definition 3.2 holds. We show condition (ii). Let $\Sigma$ be
a cycle on $\leq 2k$ edges in $H$. Consider the heaviest edge $e=\\{u,v\\}$ on
$\Sigma$.222 Ties are broken as in Algorithm 1. That is, $e$ is edge in
$\Sigma$ that appeared last in the ordering by which Algorithm 1 went over the
edges of $G$.  Then $\Sigma-e$ was already present in $H$ before $e$ was
added, forming a $u$-$v$ path of length $\leq(2k-1)w(e)$. But, before adding
$e$, we had $\operatorname{dist}_{H-F_{e}}(u,v)>(2k-1)w(e)$, so some $x\in
F_{e}$ must damage an edge of $\Sigma-e$. Thus, $(e,x)\in B\cap\Sigma$. ∎

######  Remark 3.4.

In fact, in the following proof of Theorem 3.1, we only use that the output
graph of the FT-greedy algorithm admits a small blocking set, as shown in
Lemma 3.3. That is, our proof shows that if $H$ is some $n$-vertex graph that
admits a $2k$-blocking set $B$ where each edge $e\in E(H)$ participates in at
most $f$ pairs $(e,x)\in B$, then $|E(H)|$ can be bounded from above in the
E/V/MCFT settings as stated in Theorem 3.1.

######  Remark 3.5.

Note that Lemma 3.3 stays true also for subgraphs of $H$, by deleting the
pairs from $B$ that correspond to the edges missing in the subgraph.

To analyze the size of $H$, we consider the expected number of edges in a
randomly-formed subgraph $\hat{H}_{S}$ of $H$, which we call a _random blocked
subgraph_. Informally, we bound this expectation from below by
$|E(H)|/\operatorname{poly}(f)$, and from above by a function of $n,f$ alone.
Rearranging yields the final bounds.

######  Definition 3.6 ($p$-Random Blocked Subgraph).

Let $S\subseteq\mathcal{F}$ be a random subset obtained by sampling each
$x\in\mathcal{F}$ into $S$ independently with probably $p$. Consider $H[S]$,
the subgraph of $H$ obtained by removing all edges that are damaged by
$\mathcal{F}-S$. Essentially, the _$p$ -random blocked subgraph_ $\hat{H}_{S}$
is obtained from $H[S]$ by removing the edges of surviving elements of the
blocking set. Formally:

$\displaystyle B_{S}$ $\displaystyle=\\{(e,x)\in B\mid e\in E(H[S]),x\in
S\\},$ $\displaystyle E(B_{S})$ $\displaystyle=\\{e\mid(e,x)\in B_{S}\text{
for some $x\in S$}\\},$ $\displaystyle\hat{H}_{S}$
$\displaystyle=H[S]-E(B_{S}).$

The number of edges in $\hat{H}_{S}$ is denoted by $\hat{m}$.

The point of this process is the following:

######  Observation 3.7.

A $p$-random blocked subgraph $\hat{H}_{S}$ has girth $\geq 2k+1$ with
probability $1$.

###### Proof.

Suppose $\Sigma$ is a cycle of $\leq 2k$ edges in $H[S]$ (and thus also in
$H$). As $B$ is a blocking set, there is some $(e,x)\in B\cap\Sigma$. Since
$\Sigma$ is sampled into $H[S]$, then $e\in E(H[S])$ and $x\in S$, showing
that $(e,x)\in B_{S}$. Thus, $e$ is removed in $\hat{H}_{S}$, so $\Sigma$ does
not survive in $\hat{H}_{S}$. ∎

###  3.2 The ECFT Setting

We start by analyzing the ECFT setting, in which a trivial analysis yields
optimal results. It serves as a good warm-up for the other settings. The
analysis uses the folklore _Moore Bounds_ :

######  Lemma 3.8 (Moore Bounds).

An $n$-vertex graph with girth $\geq 2k+1$ has $O(n^{1+1/k})$ edges.

Now, let $\hat{H}_{S}$ be a $1/(2f)$-random blocked subgraph. Consider an edge
$e\in E(H)$ of the FT greedy spanner $H$. Clearly, $e\in H[S]$ iff $c(e)\in
S$, which happens with probability $1/(2f)$. Next, consider a pair $(e,c)\in
B$. As $c$ does not damage $e$, meaning $c(e)\neq c$, then $(e,c)\in B_{S}$
iff both $c$ and $c(e)$ are sampled, which happens with probability
$1/(2f)^{2}$. Thus,

$\displaystyle\mathbb{E}[\hat{m}]$
$\displaystyle=\mathbb{E}\Big{[}\big{|}E\big{(}H[S]\big{)}-E(B_{S})\big{|}\Big{]}$
$\displaystyle\geq\mathbb{E}\Big{[}\big{|}E\big{(}H[S]\big{)}\big{|}-|B_{S}|\Big{]}=\frac{m}{2f}-\frac{|B|}{4f^{2}}$
$\displaystyle\geq\frac{m}{2f}-\frac{fm}{4f^{2}}=\frac{m}{4f}~{}.$ (Lemma 3.3)

On the other hand, by 3.7, $\hat{H}_{S}$ has girth $\geq 2k+1$, and thus by
the Moore bounds (Lemma 3.8), $\hat{m}=O(n^{1+1/k})$. Hence,

$\frac{m}{4f}\leq\mathbb{E}[\hat{m}]=O(n^{1+1/k})\quad\implies\quad
m=O(fn^{1+1/k}).$

This concludes the proof of Theorem 3.1(1).

######  Remark 3.9.

The proof works seamlessly for multi-graphs, and the same holds for all other
proofs in this section.

###  3.3 The VCFT Setting

We now analyze the size of the spanner produced by the greedy algorithm
(Algorithm 1) in the VCFT setting. As explained in Section 1.2, a naïve
adaptation of the proof in the ECFT setting gives an $O(f^{2}n^{1+1/k})$
bound. To get our tight bound here, we go in a different route.

####  3.3.1 Bipartite Moore Bounds

Our analysis for the VCFT setting relies on Moore Bounds for bipartite graphs.
For our purposes, the strongest known bounds of Hoory [Hoo02] are not
required, and the following weaker but simpler-to-prove bound is sufficient.

######  Lemma 3.10 (Weak Bipartite Moore Bounds).

Let $G$ be a bipartite graph with bipartition $V=L\cup R$, $|L|=x$, $|R|=y$.
Suppose $G$ has girth $\geq 2k+1$. Then $|E(G)|=O(x^{1/k}y+xy^{1/k})$.

###### Proof.

Suppose $x\leq y$. We will prove that $|E(G)|=O(x^{1/k}y)$, which implies the
lemma.

Let $S\subseteq R$ be a uniformly random subset with $|S|=x$. The expected
number of edges in the induced subgraph $G_{S}=G[L\cup S]$ is

$\sum_{e\in E(G)}\Pr[e\in L\times S]=|E(G)|\cdot\frac{x}{y}~{}.$

Choose some $S$ exceeding the expectation, i.e., such that

$|E(G_{S})|\geq|E(G)|\cdot\frac{x}{y}~{}.$ (1)

As $G_{S}$ also has girth $\geq 2k+1$, the Moore Bounds (Lemma 3.8) imply

$|E(G_{S})|\leq O(|V(G_{S})|^{1+1/k})=O(x^{1+1/k}).$ (2)

Combining Eqns. 1 and 2 yields $|E(G)|=O(x^{1/k}y)$, which concludes the
proof. ∎

####  3.3.2 Setting Up the Stage

As before, let $H$ denote the output of the greedy spanner (Algorithm 1), now
in the VCFT setting. Again, denote $m=|E(H)|$. We now perform a “clean-up”
phase for the sake of analysis, where we neglect some fraction of the edges of
$H$, as follows.

First, we claim that $H$ contains at most $O(n^{1+1/k})$ _monochromatic_
edges. Let $E_{mono}\coloneqq\\{\\{u,v\\}\in E(H)\mid c(u)=c(v)\\}$. Note that
$E_{mono}$ cannot contain cycles of $\leq 2k$ edges, as such cycles must
contain some pair $(e=\\{u,v\\},c)$ of the blocking set $B$, but
$|\\{c,c(u),c(v)\\}|\geq 2$. Hence, by the Moore Bounds (Lemma 3.8),
$|E_{mono}|=O(n^{1+1/k})$.

From now on, we assume that $H$ has no monochromatic edges. Namely, $H$ is
henceforth $H-E_{mono}$. This is justified as we can delete the $O(n^{1+1/k})$
edges of $E_{mono}$ (which is less than the upper bound we prove), while still
maintaining a small blocking set (recall Remark 3.5).

Next, for our analysis, we would like to “make” $H$ into a bipartite graph
with the special property that all the vertices of any specific color class
always lie on the same side. To obtain this, we observe the following:

######  Observation 3.11.

There is a partition $V(H)=L\cup R$, such that:

  * (i)

For every color $c$, all vertices with color $c$ are found only in one of
$L,R$.

  * (ii)

The number of edges between $L$ and $R$ is at least $|E(H)|/2$.

###### Proof.

Independently for every color $c$, with probability $1/2$, all the $c$-colored
vertices go to $L$, and otherwise they go to $R$. Each edge is split between
$L,R$ with probability $1/2$ (as it is not monochromatic). Thus, the
_expected_ number of $L$-to-$R$ edges is $|E(H)|/2$, and some partition
achieves $\geq|E(H)|/2$ many $L$-to-$R$ edges. ∎

Let $H^{\prime}$ be the subgraph of $H$ obtained by deleting all edges that
violate the bipartition. Clearly, by (ii) of the last observation, it is
enough to prove that $|E(H^{\prime})|=O(f^{1-1/k}n^{1+1/k})$. So from now on
(justified again by Remark 3.5), we assume that $H$ has only $L$-to-$R$ edges.

####  3.3.3 Bounding the Size of $H$

Again, denote $m=|E(H)|$. The following is the key lemma of the analysis:

######  Lemma 3.12.

Let $\hat{H}_{S}$ be a $p$-random blocked subgraph. Then
$\mathbb{E}[\hat{m}]=O((pn)^{1+1/k})$.

###### Proof.

Let $L_{S}=\\{v\in L\mid c(v)\in S\\}$, i.e., the vertices from $L$ whose
colors were sampled. Define $R_{S}$ similarly. The crux of the special color-
bipartition is ensuring that $|L_{S}|$ and $|R_{S}|$ are _independent_ random
variables. Recall that by 3.7, $\hat{H}_{S}$ has girth $\geq 2k+1$. Using the
bipartite Moore Bounds (Lemma 3.10), we now obtain

$\displaystyle\mathbb{E}[\hat{m}]$ $\displaystyle\leq
O\left(\mathbb{E}\left[|L_{S}|^{1/k}\cdot|R_{S}|+|L_{S}|\cdot|R_{S}|^{1/k}\right]\right)$
$\displaystyle=O\left(\mathbb{E}\left[|L_{S}|^{1/k}\right]\cdot\mathbb{E}\left[|R_{S}|\right]+\mathbb{E}\left[|L_{S}|\right]\cdot\mathbb{E}\left[|R_{S}|^{1/k}\right]\right)$
(Independence) $\displaystyle\leq
O\left(\mathbb{E}[|L_{S}|]^{1/k}\cdot\mathbb{E}[|R_{S}|]+\mathbb{E}[|L_{S}|]\cdot\mathbb{E}[|R_{S}|]^{1/k}\right)$
(Jensen’s inequality) $\displaystyle=O\left((p|L|)^{1/k}\cdot
p|R|+p|L|\cdot(p|R|)^{1/k}\right)$ $\displaystyle\leq
O\left((pn)^{1+1/k}\right)$

as required. ∎

We are now ready to complete the analysis. Let $\hat{H}_{S}$ be a $p$-random
blocked subgraph with $p=1/(2f)$. Then,

$\mathbb{E}[\hat{m}]\geq\mathbb{E}\left[|E(H[S])|-|B_{S}|\right]=\frac{m}{4f^{2}}-\frac{|B|}{8f^{3}}\geq\frac{m}{8f^{2}}~{},$

where the last inequality is by Lemma 3.3. Combining with Lemma 3.12, we now
obtain

$\frac{m}{8f^{2}}\leq\mathbb{E}[\hat{m}]=O\Big{(}\Big{(}\frac{n}{f}\Big{)}^{1+1/k}\Big{)}\quad\implies\quad
m=O(f^{1-1/k}n^{1+1/k}).$

Thus, we have proved Theorem 3.1(2).

###  3.4 The MCFT Setting

For the mixed setting, we suitably mix arguments from the ECFT and VCFT
settings. We use the same paradigm of the VCFT proof: “clean-up”, color-
partition, and applying bipartite Moore Bounds. The only step of the paradigm
that needs to be adapted is the “clean-up” phase of monochromatic edges, which
we now prove:

######  Lemma 3.13.

$H$ has at most $O(fn^{1+1/k})$ edges $e=\\{u,v\\}\in E(H)$ with $c(u)=c(v)$.

###### Proof.

Let $E^{\prime}=\\{e=\\{u,v\\}\in E(H)\mid c(u)=c(v)\\}$, and let
$H^{\prime}=(V(H),E^{\prime})$. I.e., $H^{\prime}$ is the subgraph with only
the edges that have endpoints of the same color. Notice that each connected
component of $H^{\prime}$ contains vertices with only one color.

Consider $B^{\prime}=\\{(e,c)\in B\mid e\in E^{\prime}\\}$. Each edge of
$H^{\prime}$ participates in $\leq f$ pairs from $B^{\prime}$. We claim that
$B^{\prime}$ is a $2k$-blocking set for $H^{\prime}$ in the ECFT setting
(i.e., when we ignore the existence of vertex colors). Condition (i) from
Definition 3.2 is clear. For Condition (ii), let $\Sigma$ be a cycle on $\leq
2k$ edges in $H^{\prime}$. As $B$ is a $2k$-blocking set for $H$, there exists
$(e,c)\in B$ such that the edge $e$ and the color $c$ (which does not damage
$e$) both appear on $\Sigma$. All vertices on $\Sigma$, including the
endpoints of $e$, have the same color. Thus, $c$ must appear on an _edge_ of
$\Sigma$. Therefore, the pair $(e,c)\in B^{\prime}$ certifies that Condition
(ii) holds for $\Sigma$ in the ECFT setting.

Finally, as explained in Remark 3.4, our proof of Theorem 3.1(1) showed that
in the ECFT setting, an $n$-vertex graph that has a blocking set where each
edge appears in at most $f$ pairs could only have $O(fn^{1+1/k})$ edges.
Applying this to $H^{\prime}$, we obtain that
$|E^{\prime}|=|E(H^{\prime})|=O(fn^{1+1/k})$. ∎

By the above lemma (and Remark 3.5), we can assume $H$ has no edges with
endpoints of the same color. For such $H$, we can apply the bipartitioning
procedure as in the VCFT setting (ignoring the edge colors), and restrict the
analysis to the resulting graph. By applying Lemma 3.12 on the $p$-random
blocked subgraph $\hat{H}_{S}$, we conclude that
$\mathbb{E}[\hat{m}]=O\left((pn)^{1+1/k}\right)$.

We set $p=1/(2f)$. Our final step, as before, is to give a lower bound on
$\mathbb{E}[\hat{m}]$. Let

$\displaystyle E_{2}$ $\displaystyle=\big{\\{}e=\\{u,v\\}\in E(H)\ \mid\
|\\{c(e),c(u),c(v)\\}|=2\big{\\}}$ $\displaystyle E_{3}$
$\displaystyle=\big{\\{}e=\\{u,v\\}\in E(H)\ \mid\
|\\{c(e),c(u),c(v)\\}|=3\big{\\}}$

As every edge has two different colors on its endpoints, $E(H)=E_{2}\cup
E_{3}$. Next, let $B_{2}=\\{(e,x)\in B\mid e\in E_{2}\\}$ and $B_{3}=B-B_{2}$.
By Lemma 3.3, $|B_{2}|\leq f|E_{2}|$ and $|B_{3}|\leq f|E_{3}|$. We now
calculate:

$\displaystyle\mathbb{E}[\hat{m}]$
$\displaystyle\geq\mathbb{E}\left[|E(H[S])|-|B_{S}|\right]$
$\displaystyle=\Big{(}\frac{|E_{2}|}{4f^{2}}-\frac{|B_{2}|}{8f^{3}}\Big{)}+\Big{(}\frac{|E_{3}|}{8f^{3}}-\frac{|B_{3}|}{16f^{4}}\Big{)}$
$\displaystyle\geq\frac{|E_{2}|}{8f^{2}}+\frac{|E_{3}|}{16f^{3}}\geq\frac{m}{16f^{3}}.$

Concluding, we get

$\frac{m}{16f^{3}}\leq\mathbb{E}[\hat{m}]=O\Big{(}\Big{(}\frac{n}{f}\Big{)}^{1+1/k}\Big{)}\quad\implies\quad
m=O(f^{2-1/k}n^{1+1/k}),$

which proves Theorem 3.1(3).

##  4 Lower Bounds

Our lower bounds are conditioned on the famous _Erdős Girth Conjecture_
[Erd63]:

######  Conjecture 4.1 (Erdős Girth Conjecture).

For every integers $n,k\geq 1$, there exists an $n$-vertex graph with girth at
least $2k+2$ and $\Omega(n^{1+1/k})$ edges.

The Girth Conjecture is widely believed and commonly used as a basis for lower
bounds on spanners, and particularly for the lower bounds of [BDPW18] on
V/EFT-spanners.

We start by proving a lower bound in the edge-colored case for _simple_ graphs
(see Appendix A for a discussion on multi-graphs).

######  Theorem 4.1.

Let $n,k,f\geq 1$ be integers. Assuming the Girth Conjecture, there exists a
_simple_ graph $G$ with $n$ vertices and colored edges, such that every
$f$-ECFT $(2k-1)$-spanner of $G$ must have
$\Omega(\min\\{fn^{1+1/k},n^{2}\\})$ edges.

###### Proof.

Without loss of generality, we assume $f\leq\frac{1}{8}n^{1-1/k}$. If $f$ is
larger, use the graph constructed for $\frac{1}{8}n^{1-1/k}$ color faults,
which already gives the desired bound.

Let $G_{ER}$ be the graph from the Girth Conjecture with $n$ vertices, i.e.,
it has girth $\geq 2k+2$ and $\alpha n^{1+1/k}$ edges, where $\alpha>0$ is a
fixed constant. Without loss of generality, we may assume $\alpha\leq 1$
(otherwise, delete edges from $G_{ER}$). We prove that for every $1\leq i\leq
f$, there exists a _simple_ $n$-vertex edge-colored graph $G_{i}$, with color
palette $[i]$, such that the following conditions hold:

  * (i)

The number of edges in $G_{i}$ satisfies $i\cdot\frac{\alpha}{2}\cdot
n^{1+1/k}\leq|E(G_{i})|\leq i\cdot\alpha\cdot n^{1+1/k}.$

  * (ii)

For every color $c\in[i]$, there is no cycle of $\leq 2k+1$ $c$-colored edges
in $G_{i}$.

The desired graph for the theorem is $G_{f}$, as it has $\Omega(fn^{1+1/k})$
edges by (i), and no proper subgraph which is an $f$ color fault-tolerant
$(2k-1)$-spanner by (ii).

The proof is by induction on $i$. The base case is just $G_{1}=G_{ER}$ with
all edges having the same color $1$. The induction step constructs $G_{i+1}$
from $G_{i}$, as follows. Consider a uniformly random bijection (or
permutation) $\pi:V(G_{ER})\to V(G_{i})$. For every edge $\\{u,v\\}\in
E(G_{ER})$,

$\Pr\big{[}\\{\pi(u),\pi(v)\\}\in
E(G_{i})\big{]}=\frac{|E(G_{i})|}{\binom{n}{2}}\leq\frac{i\cdot\alpha
n^{1+1/k}}{\frac{1}{4}n^{2}}\leq\frac{\frac{1}{8}n^{1-1/k}\cdot\alpha
n^{1+1/k}}{\frac{1}{4}n^{2}}\leq\frac{1}{2}.$

Thus, in expectation, at least half of the edges in $G_{ER}$ are mapped by
$\pi$ to _non-edges_ in $G_{i}$. Choose $\pi$ such that this last property
holds. Define $G_{i+1}$ by adding these edges to $G_{i}$, and color them with
the new color $i+1$. The resulting graph $G_{i+1}$ is indeed simple, and
properties (i) and (ii) follow immediately by the construction and the
induction hypothesis. ∎

For the sake of completeness, we note that the lower bound of Bodwin et al.
[BDPW18] for VFT spanners also applies to the more general VCFT setting.

######  Theorem 4.2 ([BDPW18]).

Let $n,k,f\geq 1$ be integers, $f\leq n$. Assuming the Girth Conjecture, there
exists vertex-colored simple $n$-vertex graph $G$, such that every $f$-V(C)FT
$(2k-1)$-spanner of $G$ must have $\Omega(f^{1-1/k}n^{1+1/k})$ edges.

Finally, we give the lower bound in the MCFT setting:

######  Theorem 4.3.

Let $n,k,f\geq 1$ be integers. Assuming the Girth Conjecture, there exists a
_simple_ graph $G$ with $n$ vertices, where both edges and vertices are
colored, such that every $f$-MCFT $(2k-1)$-spanner of $G$ must have
$\Omega(\min\\{f^{2-1/k}n^{1+1/k},n^{2}\\})$ edges.

###### Proof.

Let $G_{EC}$ be the edge-colored $n$-vertex graph of Theorem 4.1, with
$\Omega(\min\\{fn^{1+1/k},n^{2}\\})$ edges and no proper $f$-ECFT
$(2k-1)$-spanner. Denote its color palette by $\mathcal{C}_{E}$. We may also
assume that $G_{EC}$ is bipartite, as every graph can be made bipartite by
deleting at most half of its edges.333 This can be seen by considering a
random bipartition.  Let $V(G_{EC})=L\cup R$ be the partition to left and
right sides.

We construct a graph $G$ with both edge and vertex colors, as follows. The
vertex set is

$V(G)=(L\times[f])\cup(R\times[f]),$

i.e., there are $f$ copies of each vertex from $V(G)=L\cup R$. There are two
sets of new colors for the vertices (disjoint from each other and from
$\mathcal{C}_{E}$):

$\mathcal{C}_{L}=\\{\ell_{1},\dots,\ell_{f}\\}\quad\text{and}\quad\mathcal{C}_{R}=\\{r_{1},\dots,r_{f}\\}.$

A vertex $(u,i)\in L\times[f]$ gets the color $\ell_{i}$. Similarly, a vertex
$(v,j)\in R\times[f]$ gets the color $r_{j}$. We then place a copy of $G_{EC}$
on $(L\times\\{i\\})\cup(R\times\\{j\\})$ for every $i,j\in[f]$. Formally, the
edge set is defined by

$E(G)=\big{\\{}\\{(u,i),(v,j)\\}\mid i,j\in[f],~{}u\in L,~{}v\in
R,~{}\\{u,v\\}\in E(G_{EC})\big{\\}}.$

Every edge $\\{(u,i),(v,j)\\}\in E(G)$ is assigned the color that is given in
$G_{EC}$ to the corresponding edge $\\{u,v\\}$ (from the palette
$\mathcal{C}_{E}$). Note that the copies are edge-disjoint, so the resulting
$G$ is simple.

We now show that $G$ has no $3f$-MCFT $(2k-1)$-spanner but itself. Indeed,
suppose $H$ is such a spanner. Choose any $i,j\in[f]$. Let
$F_{L}^{i}=\mathcal{C}_{L}-\\{\ell_{i}\\}$ and
$F_{R}^{j}=\mathcal{C}_{R}-\\{r_{j}\\}$. Consider the graph $H-(F_{L}^{i}\cup
F_{R}^{j})$. As $|F_{L}^{i}\cup F_{R}^{j}|\leq 2f$, this graph must be an
$f$-MCFT (and, as
$(\mathcal{C}_{L}\cup\mathcal{C}_{R})\cap\mathcal{C}_{E}=\emptyset$, also
$f$-ECFT) $(2k-1)$-spanner of $G-(F_{L}^{i}\cup F_{R}^{j})$. However,
$G-(F_{L}^{i}\cup F_{R}^{j})$ is just the copy of $G_{EC}$ on
$(L\times\\{i\\})\cup(R\times\\{j\\})$, which has no such spanner but itself.
Therefore, each of the copies of $G_{EC}$ must be contained in $H$, hence
$H=G$ as claimed.

Finally, we have that $|V(G)|=f|V(G_{EC})|=fn$ and

$|E(G)|=f^{2}|E(G_{EC})|=f^{2}\cdot\Omega(\min\\{fn^{1+1/k},n^{2}\\})=\Omega(\min\\{f^{2-1/k}(fn)^{1+1/k},(fn)^{2})\\}).$

The result follows by rescaling the proof: $n\leftarrow fn$ and $f\leftarrow
3f$. ∎

##  5 Efficient Constructions

We now show an efficient (polynomial time) construction yielding E/V/MCFT
spanners whose sizes match the bounds of Section 3 up to a
$\operatorname{poly}(k)$ factor:

######  Theorem 5.1.

There is a polynomial time algorithm for constructing $f$-CFT
$(2k-1)$-spanners, yielding spanner with size $s$ such that:

  1. 1.

$s=O(kfn^{1+1/k})$ in the ECFT setting,

  2. 2.

$s=O(kf^{1-1/k}n^{1+1/k})$ in the VCFT setting, and

  3. 3.

$s=O(k^{2}f^{2-1/k}n^{1+1/k})$ in the MCFT setting.

The running time is $O(mf\cdot s)$.

This is by modifying the “Modified FT Greedy Spanner” algorithm of Dinitz and
Robelle [DR20] to the colored settings. As in [DR20], we start by considering
the case where $G$ is _unweighted_. Assume this from now on; we discuss how
weights are handled at the end of this section.

##### The High-Level Idea.

Consider the beginning of some iteration of the FT greedy algorithm (Algorithm
1), which examines $e=\\{u,v\\}\in E(G)$. The intractable part of the
algorithm is trying to find a fault-set $F_{e}$ of size $\leq f$ such that
$\operatorname{dist}_{H-F_{e}}(u,v)>2k-1$. If no such set is found, $e$ can
clearly be discarded. In the complementary case, $e$ is added to $H$, and the
set $F_{e}$ serves to account for $\leq f$ pairs in the $2k$-blocking set
constructed by Lemma 3.3, which ultimately yields the size bound on the final
$H$.

Dinitz and Robelle’s idea is replacing this by tractable _approximate_
subroutine, that settles for finding a set $\tilde{F}_{e}$ with size $O(kf)$,
and ensures that $e$ can be discarded if such a set is not found. This
subroutine is based on _another greedy approach_ , of computing a maximal set
of ‘disjoint’ (in some sense) $u$-$v$ paths of length $\leq 2k-1$ in $H$. The
“blame set” $\tilde{F}_{e}$ is found if the maximal set of paths contains at
most $f$ paths, in which case $e$ is inserted to the spanner. If there are
more than $f$ ‘disjoint’ paths, $e$ can be safely discarded. Dinitz and
Robelle [DR20] consider the VFT setting, where ‘disjoint’ means internally
vertex-disjoint, and the set $\tilde{F}_{e}$ contains the internal vertices of
those paths. This approach can easily be adapted to the colored setting, as we
now explain.

##### Subroutine for Deciding on an Edge.

The subroutine works in $f+1$ iterations. We preserve the invariant that if we
completed iteration $i$ without halting, then we have $i$ $u$-$v$ paths
$\\{P_{j}\\}_{j=1}^{i}$ in $H$, each of length $\leq 2k-1$. Furthermore, let
$\mathcal{C}_{j}$ be the set of colors appearing on $P_{j}$ that do not damage
$e$. Then the color sets $\\{\mathcal{C}_{j}\\}_{j=1}^{i}$ are mutually
disjoint. To execute iteration $i$, we compute the shortest $u$-$v$ path
$P_{i}$ in $H-\bigcup_{j=1}^{i-1}\mathcal{C}_{j}$. If $P_{i}$ is of length
$\geq 2k$, we halt by deciding to include $e$, and ‘blame’ the set
$\tilde{F}_{e}=\bigcup_{j=1}^{i-1}\mathcal{C}_{j}$ for this decision.
Crucially, we can bound $|\tilde{F}_{e}|\leq 4kf$ (as a path of length $\leq
2k-1$ can have at most $(2k-1)+2k$ vertices and edges, and thus at most $4k$
different colors). Otherwise, if $P_{i}$ has length $\leq 2k-1$, we add
$P_{i}$ and continue to the next iteration. If the last iteration $f+1$ was
completed, we have found $f+1$ $u$-$v$ paths of length $\leq 2k-1$, of which
every pair may share only the colors that damage $e$. This means that no set
of at most $\leq f$ color faults (that does not damage $e$ itself) can cause
the distance between $u,v$ in $H$ to be $>2k-1$. In this case, we call $e$
_replaceable_ , and we safely discard it while ensuring the correctness of the
final output spanner.

The pseudo-code for the modified FT greedy algorithm using this subroutine
appears as Algorithm 2. The running time analysis is identical to [DR20].

Algorithm 2 $\mathsf{ModifiedCFTGreedySpanner}(G,k,f)$

(Assuming $G$ is unweighted)

1:$H\leftarrow(V(G),\emptyset)$

2:for each $e=\\{u,v\\}\in E(G)$ in arbitrary order do

3: if $e$ is not replaceable because of color set $\tilde{F}_{e}$ then

4: $H\leftarrow H\cup\\{e\\}$

5:return $H$

##### Size Analysis.

The size analysis requires only minor modifications compared to the one for
the (exponential-time) FT greedy algorithm, presented in Section 3. We define

$\tilde{B}=\\{(e,c)\mid e\in E(H),c\in\tilde{F}_{e}\\}.$

Since right before an edge $e=\\{u,v\\}$ is inserted into $H$ we have that
$\operatorname{dist}_{H-\tilde{F}_{e}}(u,v)>2k-1$, then by the same proof as
in Lemma 3.3, $\tilde{B}$ is a $2k$-blocking set. We can now repeat the
analysis via random blocked subgraphs, with the following modifications:

  * (1)

The definition of a $p$-random blocked subgraph (Definition 3.6) uses
$\tilde{B}$ instead of $B$.

  * (2)

We set $p=\frac{1}{8kf}$ instead of $\frac{1}{2f}$, to account for the fact
that $|\tilde{B}|\leq 4kfm$, instead of $|B|\leq fm$.

The resulting bounds on the size of the spanner are then bigger than the ones
in Theorem 3.1 by a factor of $O(k)$ in the ECFT and the VCFT settings, and by
a factor of $O(k^{2})$ in the MCFT setting, proving Theorem 5.1 for the
unweighted case.

##### Handling Weights.

The way [DR20] handle a weighted graph $G$ works ‘as is’ also in our case. It
is surprisingly simple: Run the _unweighted_ Algorithm 2 on $G$, (i.e.,
ignoring the weights), but with the “correct” increasing order of weight. The
correctness is by the following observation: If $e=\\{u,v\\}\in G$ was found
replaceable, then at that time, for every set $F$ of at most $\leq f$ faults
(not damaging $e$), $H-F$ contains a $u$-$v$ path of at most $2k-1$ edges. All
these edges precede $e$ in the ordering, so the total weight of the path is
$\leq(2k-1)w(e)$.

##  6 Conclusion

In this work, we introduced the concept of color fault-tolerant (CFT)
spanners, which generalize vertex/edge fault-tolerant spanners. We give tight
bounds on the size required by CFT spanners, and polynomial time constructions
of such spanners with nearly optimal size guarantees. We suggest a few
possible directions for future research:

  * •

Can we provide faster algorithms for CFT spanners with size guarantees close
to those of the FT greedy algorithm? See e.g. the construction by Parter
[Par22] in the VFT setting, based on the Baswana-Sen algorithm [BS07].

  * •

As noted, the min-cut max-flow theorem does not hold in the colored setting.
Hence, one may consider investigating a different notion from the “color cuts”
of CFT-connectivity certificates, which pertains to “colorful flow”. That is,
a subgraph $H$ of $G$ such that every two vertices $u,v$ have $\lambda$ color-
disjoint paths in $G$ iff they have $\lambda$ such paths in $H$.

##### Acknowledgments.

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

## References

  * [ADD+93] Ingo Althöfer, Gautam Das, David P. Dobkin, Deborah Joseph, and José Soares.  On sparse spanners of weighted graphs.  Discret. Comput. Geom., 9:81–100, 1993.  doi:10.1007/BF02189308.
  * [BDPW18] Greg Bodwin, Michael Dinitz, Merav Parter, and Virginia Vassilevska Williams.  Optimal vertex fault tolerant spanners (for fixed stretch).  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1884–1900, 2018.  doi:10.1137/1.9781611975031.123.
  * [BDR21] Greg Bodwin, Michael Dinitz, and Caleb Robelle.  Optimal vertex fault-tolerant spanners in polynomial time.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2924–2938, 2021.  doi:10.1137/1.9781611976465.174.
  * [BDR22] Greg Bodwin, Michael Dinitz, and Caleb Robelle.  Partially optimal edge fault-tolerant spanners.  In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 3272–3286, 2022.  doi:10.1137/1.9781611977073.129.
  * [BP19] Greg Bodwin and Shyamal Patel.  A trivial yet optimal solution to vertex fault tolerant spanners.  In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC, pages 541–543, 2019.  doi:10.1145/3293611.3331588.
  * [BS04] Surender Baswana and Sandeep Sen.  Approximate distance oracles for unweighted graphs in $\tilde{O}(n^{2})$ time.  In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 271–280, 2004.  URL: http://dl.acm.org/citation.cfm?id=982792.982830.
  * [BS07] Surender Baswana and Sandeep Sen.  A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs.  Random Struct. Algorithms, 30(4):532–563, 2007.  doi:10.1002/rsa.20130.
  * [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.
  * [CKT93] Joseph Cheriyan, Ming-Yang Kao, and Ramakrishna Thurimella.  Scan-first search and sparse certificates: An improved parallel algorithms for k-vertex connectivity.  SIAM J. Comput., 22(1):157–174, 1993.
  * [CLPR10] Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty.  Fault tolerant spanners for general graphs.  SIAM J. Comput., 39(7):3403–3423, 2010.  doi:10.1137/090758039.
  * [Cow01] Lenore Cowen.  Compact routing with minimum stretch.  J. Algorithms, 38(1):170–183, 2001.  doi:10.1006/jagm.2000.1134.
  * [CW04] Lenore Cowen and Christopher G. Wagner.  Compact roundtrip routing in directed networks.  J. Algorithms, 50(1):79–95, 2004.  doi:10.1016/j.jalgor.2003.08.001.
  * [DK11] Michael Dinitz and Robert Krauthgamer.  Fault-tolerant spanners: better and simpler.  In Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC, pages 169–178, 2011.  doi:10.1145/1993806.1993830.
  * [DR20] Michael Dinitz and Caleb Robelle.  Efficient and simple algorithms for fault-tolerant spanners.  In PODC ’20: ACM Symposium on Principles of Distributed Computing, pages 493–500, 2020.  doi:10.1145/3382734.3405735.
  * [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.
  * [EEST08] Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng.  Lower-stretch spanning trees.  SIAM J. Comput., 38(2):608–628, 2008.  doi:10.1137/050641661.
  * [Erd63] Paul Erdős.  Extremal problems in graph theory.  Theory of Graphs and its Applications, 1963.
  * [FNY+20] Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai.  Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2046–2065, 2020.
  * [GK13] Mohsen Ghaffari and Fabian Kuhn.  Distributed minimum cut approximation.  In Distributed Computing - 27th International Symposium, DISC, volume 8205 of Lecture Notes in Computer Science, pages 1–15. Springer, 2013.
  * [Hoo02] Shlomo Hoory.  The size of bipartite graphs with a given girth.  J. Comb. Theory, Ser. B, 86(2):215–220, 2002.  doi:10.1006/JCTB.2002.2123.
  * [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.
  * [KM97] David R. Karger and Rajeev Motwani.  An NC algorithm for minimum cuts.  SIAM J. Comput., 26(1):255–272, 1997.
  * [Kui12] F. Kuipers.  An overview of algorithms for network survivability.  ISRN Communications and Networking, 2012, 12 2012.  doi:10.5402/2012/932456.
  * [LNP+21] Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai.  Vertex connectivity in poly-logarithmic max-flows.  In STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 317–329, 2021.
  * [Mat93] David W. Matula.  A linear time $2+\epsilon$ approximation algorithm for edge connectivity.  In Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, SODA, pages 500–504, 1993.
  * [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.
  * [Par19] Merav Parter.  Small cuts and connectivity certificates: A fault tolerant approach.  In 33rd International Symposium on Distributed Computing, DISC, volume 146 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1–30:16. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019.  doi:10.4230/LIPIcs.DISC.2019.30.
  * [Par22] Merav Parter.  Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallel.  In STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1080–1092, 2022.  doi:10.1145/3519935.3520047.
  * [PS89] David Peleg and Alejandro A. Schäffer.  Graph spanners.  J. Graph Theory, 13(1):99–116, 1989.  doi:10.1002/jgt.3190130114.
  * [PU88] David Peleg and Eli Upfal.  A tradeoff between space and efficiency for routing tables.  In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC, pages 43–52, 1988.  doi:10.1145/62212.62217.
  * [PU89] David Peleg and Jeffrey D. Ullman.  An optimal synchronizer for the hypercube.  SIAM J. Comput., 18(4):740–747, 1989.  doi:10.1137/0218050.
  * [TZ01] Mikkel Thorup and Uri Zwick.  Compact routing schemes.  In Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA, pages 1–10, 2001.  doi:10.1145/378580.378581.
  * [TZ05] Mikkel Thorup and Uri Zwick.  Approximate distance oracles.  J. ACM, 52(1):1–24, 2005.  doi:10.1145/1044731.1044732.
  * [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, 02 2011.  doi:10.1007/s10878-009-9222-0.

##  Appendix A FT Spanners for Multi-Graphs

All of the results in this paper apply also when $G$ is a colored _multi_
-graph, i.e., when many parallel edges between two vertices are allowed.
Especially in edge-colored settings, this seems like a rather natural
assumption in light of the real-world motivation of communication networks.
However, it is presumably less natural in non-colored settings, so explicit
discussions on multi-graphs have mostly been neglected in previous work on FT
spanners. We next provide such a short discussion, which shows an interesting
phenomenon: the bounds for uncolored multi-graphs are the same as for colored
simple graphs.

##### EFT: $\Theta(fn^{1+1/k})$ size bounds.

Our upper bound for ECFT-spanners in Theorem 3.1(1) applies for multi-graphs,
and EFT is just a special case. Additionally, we note that the EFT-spanner
algorithm of Chechik et al. [CLPR10] also works on multi-graphs, and achieves
this size bound. For the lower bound, one may take the Girth Conjecture graph
with $\Omega(n^{1+1/k})$ edges, and give each of its edges multiplicity $f$.
Clearly, such a graph cannot have a proper $f$-EFT $(2k-1)$-spanner.

##### VFT: $\Theta(f^{1-1/k}n^{1+1/k})$ size bounds.

In the VFT setting, parallel edges can be discarded by keeping the edge of
lowest weight among them. This does not change distances (regardless of which
vertex faults occur). Hence, the bounds are the same as for simple graphs.

##### MFT: $\Theta(f^{2-1/k}n^{1+1/k})$ size bounds.

Constructing a lower bound instance is easy: Take the VFT lower bound instance
which is a simple graph with $\Omega(f^{1-1/k}n^{1+1/k})$ edges and replace
each edge by $f$ parallel edges. Our upper bound for MCFT spanners applies
also here.

##  Appendix B Color Lists

This section is devoted to proving Theorem 1.4. We start with a formal
description of the color lists setting. Here, each edge/vertex $x\in E(G)\cup
V(G)$ is associated with a list $\ell(x)\subseteq\mathcal{C}$, where
$\mathcal{C}$ is a finite color palette. The failure of any color
$c\in\ell(x)$ causes $x$ to crash. Formally, for $c\in\mathcal{C}$, we now
denote $E_{c}(G)=\\{e\in E(G)\mid c\in\ell(e)\\}$ and $V_{c}(G)=\\{v\in
V(G)\mid c\in\ell(v)\\}$. The fault universe is $\mathcal{F}=\\{E_{c}(G)\cup
V_{c}(G)\\}_{c\in\mathcal{C}}$. Again, the elements in $\mathcal{F}$ are in
1-to-1 correspondence to the colors in $\mathcal{C}$ (that is, we have faults
of colors). We say $s\in\mathcal{F}$ damages $e=\\{u,v\\}\in E(G)$ if
$s\cap(\ell(e)\cup\ell(u)\cup\ell(v))\neq\emptyset$. As $s$ is identified with
some color $c\in\mathcal{C}$, this means that the color $c$ damages $e$ if it
appears in $\ell(e)\cup\ell(u)\cup\ell(v)$. For $S\subseteq\mathcal{F}$ (or
$S\subseteq\mathcal{C}$), the notations $G-S$ and $G[S]$ are defined as in
Section 2. In particular, note that a vertex $v\in V(G)$ such that
$\ell(v)\not\subseteq S$ becomes isolated in $G[S]$. We say that $G$ is
_$(\mu,\nu)$ -list-colored_ if $|\ell(e)|\leq\mu$ for all $e\in E(G)$, and
$|\ell(v)|\leq\nu$ for all $v\in V(G)$. Namely, edge (resp., vertex) lists are
of size at most $\mu$ (resp., $\nu$). Letting $(\mu,\nu)=(1,0)$, $(0,1)$ or
$(1,1)$ gives the ECFT, VCFT or MCFT settings, respectively. Throughout, we
will consider a $(\mu,\nu)$-list-colored graph $G$, where $\mu,\nu$ are
arbitrary fixed integer constants.

###  B.1 Upper Bound

As in Section 3, the upper bound on the size of an $f$-CFT $(2k-1)$-spanner is
obtained by analyzing the output spanner $H$ of the FT-greedy algorithm
(Algorithm 1). Observe that Lemma 3.3 still holds: $H$ has a blocking set
where each edge $e\in E(H)$ appears in at most $f$ pairs $(e,x)\in B$. Again,
this property alone suffices for proving the size upper bound. Namely, we
have:

######  Theorem B.1.

Let $H$ be a $(\mu,\nu)$-list-colored graph with $n$ vertices. Suppose there
exists a $2k$-blocking set $B$ for $H$, such that for every $e\in E(H)$, there
are at most $f$ pairs of the form $(e,c)\in B$. Then
$|E(H)|=O(f^{\mu+\nu(1-1/k)}n^{1+1/k})$.

Without loss of generality, we assume that the edge (vertex) color-lists in
$H$ are all of size _exactly $\mu$_ (_exactly $\nu$_). Otherwise, “pad” the
lists with new colors, which does not hurt the blocking set condition.
Throughout, we denote $m=|E(H)|$.

The proof of Theorem 1.4 is by induction on $\nu$, the size of the vertex
lists. As in Section 3, we analyze the expection of $\hat{m}$ number of edges
in a $p$-random blocked subgraph $\hat{H}_{S}$ (as defined in Definition 3.6),
with $p=1/(2f)$. Note that 3.7 stays true, i.e., a $p$-random blocked subgraph
always has girth $>2k$.

##### Base Case: $\nu=0$.

By the Moore Bounds (Lemma 3.8), $\mathbb{E}[\hat{m}]=O(n^{1+1/k})$. On the
other hand, note that an edge $e\in E(H)$ has probability $(2f)^{-\mu}$ to
survive in $H[S]$. Thus,

$\displaystyle\mathbb{E}[\hat{m}]\geq\mathbb{E}\Big{[}\big{|}E\big{(}H[S]\big{)}\big{|}-|B_{S}|\Big{]}=\frac{m}{(2f)^{\mu}}-\frac{|B|}{(2f)^{\mu+1}}\geq\frac{m}{2^{\mu+1}f^{\mu}}.$

Combining, we get $m\leq 2^{\mu+1}f^{\mu}\cdot
O(n^{1+1/k})=O(f^{\mu}n^{1+1/k})$, as needed.444Recall that $\mu,\nu$ are
constants.

##### Induction Step.

For $\nu>0$, we follow the strategy of the MCFT setting from Section 3. We
start with the “clean-up” phase.

######  Lemma B.2.

Let $E_{\mathsf{conf}}=\\{e=\\{u,v\\}\in
E(H)\mid\ell(u)\cap\ell(v)\neq\emptyset\\}$ be the set of _conflicting_ edges,
i.e., edges whose endpoints share a color in their lists. Then
$|E_{\mathsf{conf}}|=O(f^{\mu+(\nu-1)(1-1/k)}\cdot n^{1+1/k})$.

###### Proof.

For $c\in\mathcal{C}$, let $H_{c}$ be the subgraph of $H$ induced on
$V_{c}(H)$, i.e., on those vertices with color $c$ in their lists. Let
$n_{c}=|V_{c}(H)|$. Let $B_{c}$ the $2k$-blocking set of $H_{c}$ induced from
$B$, i.e., $B_{c}=\\{(e,x)\in B\mid e\in E(H_{c})\\}$. As $c$ damages every
edge in $E(H_{c})$, it cannot appear in $B_{c}$. Thus, we may omit $c$ from
the vertex lists of $H_{c}$, and $B_{c}$ remains a $2k$-blocking set for this
$(\mu,\nu-1)$-list-colored graph. So, by induction,
$|E(H_{c})|=O(f^{\mu+(\nu-1)(1-1/k)}n_{c}^{1+1/k})$. As
$E_{\mathsf{conf}}\subseteq\bigcup_{c}E(H_{c})$, we get
$|E_{\mathsf{conf}}|\leq\sum_{c}|E(H_{c})|=O\left(f^{\mu+(\nu-1)(1-1/k)}\cdot\sum_{c}n_{c}^{1+1/k}\right).$
Note that $\sum_{c}n_{c}^{1+1/k}\leq n^{1/k}\cdot\sum_{c}n_{c}=n^{1/k}\cdot\nu
n=O(n^{1+1/k}),$ so the lemma follows. ∎

By the above lemma, we may assume, without loss of generality, that $H$ has no
conflicting edges (i.e., $H$ is henceforth replaced with
$H-E_{\mathsf{conf}}$). The next step is the color-bipartition.

######  Observation B.3.

There is a subgraph $H^{\prime}$ of $H$ with the following properties:

  * (i)

$H^{\prime}$ is bipartite with partition $V(H^{\prime})=L\cup R$.

  * (ii)

For each color $c$, all vertices of $H^{\prime}$ that have $c$ in their lists
appear on the same side of $H^{\prime}$, namely, either in $L$ or in $R$.

  * (iii)

$|E(H^{\prime})|\geq 2^{-2\nu+1}\cdot m$.

###### Proof.

Independently for each $c\in C$, with probability $1/2$, choose the side $L$
for $c$, otherwise choose $R$. A vertex $v\in V(H)$ is deleted if the colors
in $\ell(v)$ did not all agree on the same side. Otherwise, it goes to the
agreed side in $H^{\prime}$. The probability of each edge $e\in E(H)$ to have
one endpoint in $L$ and the other in $R$, and thus survive in $H^{\prime}$, is
$2^{-2\nu+1}$ (as it is not conflicting). Thus,
$\mathbb{E}[|E(H^{\prime})|]=2^{-2\nu+1}\cdot m$, which implies the claim. ∎

As $2^{-2\nu+1}=\Theta(1)$, we may replace $H$ with $H^{\prime}$ from now on.
I.e., henceforth we assume, without loss of generality, that $H$ has a
bipartition $V(H)=L\cup R$ where for each color $c$ it holds that either
$V_{c}(H)\subseteq L$ or $V_{c}(H)\subseteq R$ (i.e., the vertices with $c$ in
their lists are all in one side). We next use the bipartite Moore bounds:

######  Lemma B.4.

Let $\hat{H}_{S}$ be a $p$-random blocked subgraph of $H$ with $\hat{m}$
edges. Then $\mathbb{E}[\hat{m}]=O((p^{\nu}n)^{1+1/k})$.

###### Proof.

The proof is identical to Lemma 3.12, but with $L_{S}=\\{v\in
L\mid\ell(v)\subseteq S\\}$, so $\mathbb{E}[|L_{S}|]=p^{\nu}|L|$, and
similarly for $R_{S}$. ∎

We are now ready to conclude the induction step. Let $\hat{H}_{S}$ be a
$p$-random blocked subgraph with $\hat{m}$ edges, where $p=1/(2f)$. For
$i\in[2\nu,2\nu+\mu]$, let

$\displaystyle E_{i}$ $\displaystyle=\\{e=\\{u,v\\}\in
E(H)\mid|\ell(e)\cup\ell(u)\cup\ell(v)|=i\\},$ $\displaystyle B_{i}$
$\displaystyle=\\{(e,c)\in B\mid e\in E_{i}\\}.$

Note that $E(H)=\bigcup_{i}E_{i}$ (as there are no conflicting edges),
$B=\bigcup_{i}B_{i}$, and $|B_{i}|\leq f|E_{i}|$. We have:

$\mathbb{E}[\hat{m}]\geq\mathbb{E}\left[|E(H[S])|-|B_{S}|\right]=\sum_{i=2\nu}^{2\nu+\mu}\Big{(}\frac{|E_{i}|}{2^{i}f^{i}}-\frac{|B_{i}|}{2^{i+1}f^{i+1}}\big{)}\geq\sum_{i=2\nu}^{2\nu+\mu}\frac{|E_{i}|}{2^{i+1}f^{i}}=\Omega\Big{(}\frac{m}{f^{2\nu+\mu}}\Big{)}.$

Combining with Lemma B.4, and rearranging yields
$m=O(f^{\mu+\nu(1-1/k)}n^{1+1/k})$, which concludes the induction step and
proves Theorem 1.4.

###  B.2 Lower Bound

The lower bound for the color lists setting is obtained by combining the
proofs of Theorem 4.1 and Theorem 4.3.

######  Theorem B.5.

Let $\mu,\nu$ be constant integers. Assuming the Girth Conjecture, there
exists a _simple_ $(\mu,\nu)$-list colored graph $G$ with $n$ vertices, such
that every $f$-CFT $(2k-1)$-spanner of $G$ must have
$\Omega(\min\\{f^{\mu+\nu(1-1/k)}n^{1+1/k},n^{2}\\})$ edges.

###### Proof sketch..

First, repeat the proof of Theorem 4.1 to create an $n$-vertex graph
$G^{\prime}$ consisting of $\binom{f+\mu}{\mu}$ edge-disjoint “Erdős graphs”
with girth $\geq 2k+2$ and $\Omega(n^{1+1/k})$ edges. Let $\mathcal{C}_{E}$ be
a set of $f+\mu$ colors. Each Erdős graph in $G^{\prime}$ is associated with a
$\mu$-subset of $\mathcal{C}_{E}$, which is the list of colors given to all
its edges.

Next, we modify the proof of Theorem 4.3 using $G^{\prime}$ as the base graph.
Again, we may assume $G^{\prime}$ is bipartite with sides $V(G^{\prime})=L\cup
R$. The lower bound graph $G$ will use the color palette
$\mathcal{C}_{E}\cup\mathcal{C}_{L}\cup\mathcal{C}_{R}$, where these sets are
disjoint, and $|\mathcal{C}_{L}|=|\mathcal{C}_{R}|=f+\nu$. The vertex set is

$V(G)=\left(L\times\binom{\mathcal{C}_{L}}{\nu}\right)\cup\left(R\times\binom{\mathcal{C}_{R}}{\nu}\right).$

For each
$s_{L}\in\binom{\mathcal{C}_{L}}{\nu},s_{R}\in\binom{\mathcal{C}_{R}}{\nu}$,
we place a copy of $G^{\prime}$ on
$(L\times\\{s_{L}\\}\cup(R\times\\{s_{R}\\})$. All vertices in
$L\times\\{s_{L}\\}$ get $s_{L}$ as their color list, and similarly for
$R\times\\{s_{R}\\}$.

Now, let $s_{E}\in\binom{\mathcal{C}_{E}}{\mu}$. Failing the $3f$ colors
$(\mathcal{C}_{E}-s_{E})\cup(\mathcal{C}_{L}-s_{L})\cup(\mathcal{C}_{R}-s_{R})$
leaves us with a single Erdős graph with girth $\geq 2k+2$. Every edge of $G$
lies in such an Erdős graph, which shows that the $(\mu,\nu)$-list-colored
graph $G$ has no proper $3f$-CFT $(2k-1)$-spanner. Note that
$\binom{f+\mu}{\mu}=\Theta(f^{\mu})$, and $\binom{f+\nu}{\nu}=\Theta(f^{\nu})$
(as $\mu,\nu$ are constants). So, $|V(G)|=\Theta(f^{\nu}n)$ vertices, and
$|E(G)|=\Theta(f^{2\nu+\mu}n^{1+1/k})=\Theta(f^{\mu+\nu(1-1/k)}|V(G)|^{1+1/k})$.
The result follows by rescaling. ∎


* [59] J.-E. Bourgine, M. Fukuda, K. Harada, Y. Matsuo, and R.-D. Zhu, “(p, q)-webs of DIM representations, 5d $\mathcal{N}=1$ instanton partition functions and qq-characters,” JHEP 11 (2017) 034, arXiv:1703.10759 [hep-th].
  * [60] J.-E. Bourgine, M. Fukuda, Y. Matsuo, and R.-D. Zhu, “Reflection states in Ding-Iohara-Miki algebra and brane-web for D-type quiver,” JHEP 12 (2017) 015, arXiv:1709.01954 [hep-th].
  * [61] H. Awata, H. Kanno, A. Mironov, A. Morozov, K. Suetake, and Y. Zenkevich, “$(q,t)$-KZ equations for quantum toroidal algebra and Nekrasov partition functions on ALE spaces,” JHEP 03 (2018) 192, arXiv:1712.08016 [hep-th].
  * [62] S. Sasa, A. Watanabe, and Y. Matsuo, “A note on the S-dual basis in the free fermion system,” PTEP 2020 no. 2, (2020) 023B02, arXiv:1904.04766 [hep-th].
  * [63] C. Beem, M. Lemos, P. Liendo, W. Peelaers, L. Rastelli, and B. C. van Rees, “Infinite Chiral Symmetry in Four Dimensions,” Commun. Math. Phys. 336 no. 3, (2015) 1359–1433, arXiv:1312.5344 [hep-th].
  * [64] K. Ito and H. Shu, “ODE/IM correspondence and the Argyres-Douglas theory,” JHEP 08 (2017) 071, arXiv:1707.03596 [hep-th].
  * [65] L. Hollands, C. A. Keller, and J. Song, “From SO/Sp instantons to W-algebra blocks,” JHEP 03 (2011) 053, arXiv:1012.4468 [hep-th].
  * [66] L. Hollands, C. A. Keller, and J. Song, “Towards a 4d/2d correspondence for Sicilian quivers,” JHEP 10 (2011) 100, arXiv:1107.0973 [hep-th].