Color fault-Tolerant spanners

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 (number of edges) 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 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/kn^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 Ω(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) Θ(f^1/2n^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 Θ(f^2-1/kn^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].