Metric decompositions are a fundamental tool in the design of algorithms involving distances. We study fast algorithms for sampling from probabilistic metric decompositions of n-point sets in 𝓁_∞ and 𝓁₂ spaces of high dimension d. For 𝓁_∞, we design a padded-decomposition algorithm that runs in time Õ(nd²), which is near-linear in n, and achieves padding parameter Õ(log n). Our algorithm constructs a new sparse neighborhood cover that is based on geometric properties of 𝓁_∞ [Indyk, JCSS'01], and utilizes recent reductions between covers and decompositions [Conroy and Filtser, STOC'25]. For 𝓁₂, we design a separating-decomposition algorithm that achieves near optimal separation Õ(√{log n}) in almost-linear time n^{1+o(1)}. Our bounds improve over known algorithms with similar running time by a factor Ω(√{log n}), and the techniques have additional applications to spanners and nearest-neighbor search.

We revisit the problem of fault-tolerant (FT) distance preservers, when failure events in the network admit a form of correlation modeled as color faults. FT distance preservers are sparse subgraphs that preserve distances between specified pairs of vertices, even after some edge or vertex failures occur. In the classical fault model, any set of at most $k$ edges or vertices might fail (where $k \geq 1$ is a given parameter). Despite extensive research, the classical model admits significant and tantalizing gaps, both in terms of sparsity bounds and of algorithmic efficiency. In this work, we study the problem in the recently introduced color fault-tolerant (CFT) model: the given graph $G=(V,E)$ has arbitrary colors on its edges/vertices where each color appears at most $k$ times, and is susceptible to color faults, where the failure of color $c$ causes all the $c$-colored elements to crash. Our main contribution is in the multi-source setting, where $G$ has a source-set $S \subseteq V$, and the CFT preserver should preserve $S \times V$ distances under any single color fault. We show the following results (where $n = |V|$, $m = |E|$): - There exists a CFT distance preserver $H$ of $G$ with $\tilde{O}(n^{2 - \frac{1}{k+1}} \cdot |S|^{\frac{1}{k+1}} )$ edges. - The above sparsity bound is worst-case optimal up to polylogarithmic terms. - There is a combinatorial randomized algorithm that produces a preserver $H$ whose size meets the above optimal sparsity bound, with running time of $\tilde{O}(m \cdot n^{1 - \frac{1}{k+1}} \cdot |S|^{\frac{1}{k+1}})$. - The above running time is conditionally optimal: a polynomial improvement would refute the combinatorial Boolean Matrix Multiplication (BMM) conjecture. Furthermore, the running time remains optimal even if we only require mild sparsification to $m^{1-ε}$ edges.

We study the succinct representations of vertex cuts by centralized oracles and labeling schemes. For an undirected \(n\)-vertex graph \(G = (V,E)\) and integer parameter \(f \ge 1\), the goal is supporting vertex cut queries: Given \(F \subseteq V\) with \(|F| \le f\), determine if \(F\) is a vertex cut in \(G\). In the centralized data structure setting, it is required to preprocess \(G\) into an \(f\)-vertex cut oracle that can answer such queries quickly, while occupying only small space. In the labeling setting, one should assign a short label to each vertex in \(G\), so that a cut query \(F\) can be answered by merely inspecting the labels assigned to the vertices in \(F\).

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 present a compact labeling scheme for determining whether a designated set of terminals in a graph remains connected after any f (or less) vertex failures occur. An f-FT Steiner connectivity labeling scheme for an n-vertex graph G = (V,E) with terminal set U ⊆ V provides labels to the vertices of G, such that given only the labels of any subset F ⊆ V with |F| ≤ f, one can determine if U remains connected in G-F. The main complexity measure is the maximum label length. The special case U = V of global connectivity has been recently studied by Jiang, Parter, and Petruschka [Yonggang Jiang et al., 2025], who provided labels of n^{1-1/f} ⋅ poly(f,log n) bits. This is near-optimal (up to poly(f,log n) factors) by a lower bound of Long, Pettie and Saranurak [Yaowei Long et al., 2025]. Our scheme achieves labels of |U|^{1-1/f} ⋅ poly(f, log n) for general U ⊆ V, which is near-optimal for any given size |U| of the terminal set. To handle terminal sets, our approach differs from [Yonggang Jiang et al., 2025]. We use a well-structured Steiner tree for U produced by a decomposition theorem of Duan and Pettie [Ran Duan and Seth Pettie, 2020], and bypass the need for Nagamochi-Ibaraki sparsification [Hiroshi Nagamochi and Toshihide Ibaraki, 1992].

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

We present succinct labeling schemes for answering connectivity queries in graphs subject to a specified number of vertex failures. An f-vertex/edge fault tolerant (f-V/EFT) connectivity labeling is a scheme that produces succinct labels for the vertices (and possibly to the edges) of an n-vertex graph G, such that given only the labels of two vertices s,t and of at most f faulty vertices/edges F, one can infer if s and t are connected in G−F. The primary complexity measure is the maximum label length (in bits). The f-EFT setting is relatively well understood: [Dory and Parter, PODC 2021] gave a randomized scheme with succinct labels of O(log3 n) bits, which was subsequently derandomized by [Izumi et al., PODC 2023] with Õ(f2)-bit labels. As both noted, handling vertex faults is more challenging. The known bounds for the f-VFT setting are far away: [Parter and Petruschka, DISC 2022] gave Õ(n1−1/2Θ(f))-bit labels, which is linear in n already for f =Ω(loglogn). In this work we present an efficient f-VFT connectivity labeling scheme using poly(f, logn) bits. Specifically, we present a randomized scheme with O(f3 log5 n)-bit labels, and a derandomized version with O(f7 log13 n)-bit labels, compared to an Ω(f)-bit lower bound on the required label length. Our schemes are based on a new low-degree graph decomposition that improves on [Duan and Pettie, SODA 2017], and facilitates its distributed representation into labels. This is accompanied with specialized linear graph sketches that extend the techniques of the Dory and Parter to the vertex fault setting, which are derandomized by adapting the approach of Izumi et al. and combining it with hit-miss hash families of [Karthik and Parter, SODA 2021]. Finally, we show that our labels naturally yield routing schemes avoiding a given set of at most f vertex failures with table and header sizes of only poly(f,logn) bits. This improves significantly over the linear size bounds implied by the EFT routing scheme of Dory and Parter.

We introduce new data structures for answering connectivity queries in graphs subject to batched vertex failures. A deterministic structure processes a batch of $d\leq d_{\star}$ failed vertices in $\tilde{O}(d^3)$ time and thereafter answers connectivity queries in $O(d)$ time. It occupies space $O(d_{\star} m\log n)$. We develop a randomized Monte Carlo version of our data structure with update time $\tilde{O}(d^2)$, query time $O(d)$, and space $\tilde{O}(m)$ for any failure bound $d\le n$. This is the first connectivity oracle for general graphs that can efficiently deal with an unbounded number of vertex failures. We also develop a more efficient Monte Carlo edge-failure connectivity oracle. Using space $O(n\log^2 n)$, $d$ edge failures are processed in $O(d\log d\log\log n)$ time and thereafter, connectivity queries are answered in $O(\log\log n)$ time, which are correct w.h.p. Our data structures are based on a new decomposition theorem for an undirected graph $G=(V,E)$, which is of independent interest. It states that for any terminal set $U\subseteq V$ we can remove a set $B$ of $|U|/(s-2)$ vertices such that the remaining graph contains a Steiner forest for $U-B$ with maximum degree $s$.

In this paper we present succinct labeling schemes for supporting connectivity queries under vertex faults. For a given $n$-vertex graph $G$, an $f$-VFT (resp., EFT) connectivity labeling scheme is a distributed data structure that assigns each of the graph edges and vertices a short label, such that given the labels of a vertex pair $u$ and $v$, and the labels of at most $f$ failing vertices (resp., edges) $F$, one can determine if $u$ and $v$ are connected in $G \setminus F$. The primary complexity measure is the length of the individual labels. Since their introduction by [Courcelle, Twigg, STACS '07], FT labeling schemes have been devised only for a limited collection of graph families. A recent work [Dory and Parter, PODC 2021] provided EFT labeling schemes for general graphs under edge failures, leaving the vertex failure case fairly open. We provide the first sublinear $f$-VFT labeling schemes for $f \geq 2$ for any $n$-vertex graph. Our key result is $2$-VFT connectivity labels with $O(\log^3 n)$ bits. Our constructions are based on analyzing the structure of dual failure replacement paths on top of the well-known heavy-light tree decomposition technique of [Sleator and Tarjan, STOC 1981]. We also provide $f$-VFT labels with sub-linear length (in $|V|$) for any $f=o(\log\log n)$, that are based on a reduction to the existing EFT labels.