We study (α,β)-spanners for weighted graphs. We propose a simple greedy completion procedure which starts from a sparse initial graph, and repeatedly fixes pairs of vertices with a bad stretch, generalizing Knudsen’s additive completion [SWAT 2014]. As an application, we construct (k,k-1)-spanners for weighted graphs of size Õ(n^{1+1/k}), which were previously unknown.

Abstract Fault-tolerant connectivity labelings are schemes that, given an n -vertex graph $$G=(V,E)$$ 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 $$\vert F\vert \le f$$ | F | ≤ f , one can determine if u , v are connected in $$G-F$$ G - F , the surviving graph after removing F . For the edge or vertex faults models, i.e., $$F\subseteq E$$ F ⊆ E or $$F \subseteq V$$ F ⊆ V , a sequence of recent work established schemes with $$\operatorname {poly}(f,\log n)$$ 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$$ 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)$$ Ω ( n ) bits. We provide a deterministic scheme with labels of $$\tilde{O}(\sqrt{n})$$ O ~ ( n ) bits in the worst case, and a matching lower bound. Moreover, our scheme is universally optimal : even schemes tailored to handle only colorings of one specific graph topology (i.e., may store the topology “for free”) cannot produce asymptotically smaller labels. We characterize the optimal length by a new graph parameter $$\textsf{bp}(G)$$ 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}(\textsf{bp}(G))$$

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].

We provide new algorithms for constructing spanners of arbitrarily edge- or vertex-colored graphs, that can endure up to f failures of entire color classes. The failure of even a single color may cause a linear number of individual edge/vertex faults. This model, related to the notion of hedge connectivity, arises in many practical contexts such as optical telecommunication and multi-layered networks.

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 spanners, revealing an interesting phenomenon: while (individual) edge faults are "easier" than vertex faults in terms of spanner size, 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].