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 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 et al. [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 results further extend to the color lists model, where every edge/vertex is given a list of colors, and the failure of any color from the list makes the edge/vertex crash. 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].