Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time
This work addresses the problem of fault-tolerant distance preservers under correlated failures, providing tight bounds and conditionally optimal algorithms that advance the theoretical understanding of network resilience.
This paper introduces color fault-tolerant distance preservers, where failures are correlated via colors, and provides optimal sparsity bounds and conditionally optimal algorithms for multi-source settings. The main result is a preserver with Õ(n^{2-1/(k+1)} |S|^{1/(k+1)}) edges and a matching lower bound, along with a combinatorial algorithm running in Õ(m n^{1-1/(k+1)} |S|^{1/(k+1)}) time, which is optimal under the BMM conjecture.
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.