pith. sign in

arxiv: 2504.17868 · v2 · submitted 2025-04-24 · 💻 cs.DS

Color Fault-Tolerant Distance Preservers: \~{O}ptimal Size in Conditionally \~{O}ptimal Time

Merav Parter , Asaf Petruschka This is my paper

Pith reviewed 2026-05-22 17:49 UTC · model grok-4.3

classification 💻 cs.DS
keywords fault-tolerant distance preserverscolor faultsgraph algorithmssparsity boundsconditional optimalityBoolean matrix multiplicationcombinatorial algorithms
0
0 comments X

The pith

Color fault-tolerant distance preservers can be constructed with optimal sparsity in conditionally optimal time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper develops methods for building fault-tolerant distance preservers in a model where failures are correlated through edge or vertex colors. In this color fault model, each color is used at most k times, and a fault disables all elements of one color. The authors prove that a preserver for distances from a source set S to all vertices, resilient to any single color fault, can have as few as Õ(n^{2 - 1/(k+1)} ⋅ |S|^{1/(k+1)}) edges. This size is optimal up to polylog factors. They also give a randomized algorithm to construct such a preserver in Õ(m ⋅ n^{1 - 1/(k+1)} ⋅ |S|^{1/(k+1)}) time, which is conditionally optimal under the combinatorial Boolean matrix multiplication conjecture.

Core claim

The central discovery is a color fault-tolerant distance preserver H for a graph G with source set S that preserves all S to V distances under any single color fault and has Õ(n^{2 - 1/(k+1)} ⋅ |S|^{1/(k+1)}) edges. This bound is worst-case optimal up to polylogarithmic terms. Moreover, H can be constructed by a combinatorial randomized algorithm running in Õ(m ⋅ n^{1 - 1/(k+1)} ⋅ |S|^{1/(k+1)}) time, and this time is the best possible unless the combinatorial BMM conjecture is false.

What carries the argument

The key mechanism is the color fault model, where correlated failures are limited to all elements sharing a color, with each color appearing at most k times, allowing for sparsity bounds derived from this multiplicity.

If this is right

  • The sparsity bound is tight in the worst case.
  • The construction algorithm achieves the sparsity in the stated time.
  • The time bound holds even for producing a preserver with only m^{1-ε} edges.
  • These results apply specifically to the multi-source single color fault setting.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the color model accurately captures real-world failure correlations, then these preservers could improve network resilience designs.
  • The conditional optimality under BMM suggests similar time barriers may apply to other distance preservation problems in graphs.
  • Extending the approach to handle multiple simultaneous color faults could be a natural next step for more robust fault tolerance.

Load-bearing premise

The load-bearing premise is that faults affect entire colors at once, with no color used more than k times, which enables the specific sparsity and time bounds.

What would settle it

Demonstrating a graph and source set where any single-color-fault preserver requires asymptotically more than n^{2 - 1/(k+1)} |S|^{1/(k+1)} edges, or developing a faster algorithm for the construction that does not violate the BMM conjecture.

Figures

Figures reproduced from arXiv: 2504.17868 by Asaf Petruschka, Merav Parter.

Figure 1
Figure 1. Figure 1: Illustration: third inductive step. Faulty edges of color [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Construction of the tree T(∆ = 2, q = 3). T1, T2 and T3 are copies of T(1, 3) with disjoint colors. The corresponding color cv for each leaf v is shown beneath it. (c) T has q ∆ leaves. (d) Each leaf in T has depth at least d(∆, q) := q ∆ − 1 and at most D(∆, q) := 2(q ∆ − 1). (e) The number of edge in T is N(∆, q) = ∆(q ∆+1 − q ∆−1 ). Proof. By induction on ∆. For the base case, is T(0, q) is a single ver… view at source ↗
Figure 3
Figure 3. Figure 3: The graph G from Theorem 4.4. The graph G∗ with pairs P ∗ = {(xi , yi)} n i=1 form a worst-case instance for DP(n, n), reweighted so that all distances in G∗ are smaller than 1. If j ̸= i or k ̸= i, then such a path must have weight at least (n − j) + (n − k) ≥ 2(n − i) + 1. Conversely, if we take j = k = i and use the shortest xi ⇝ yi path in G∗ , the path has weight 2(n−i) + distG∗ (xi , yi) < 2(n−i) + 1… view at source ↗
Figure 4
Figure 4. Figure 4: Construction of the tree T(∆ = 3). T0 and T1 are copies of T(2) with disjoint colors. The corresponding color cv for each leaf v is shown beneath it. Proof. By induction on ∆. The base case ∆ = 0 is just a single vertex v, which is both the root and the leaf, and some color cv (that does not appear on T(0), as there are no edges). For the induction step, we construct T = T(∆) from T(∆ − 1) as follows. Let … view at source ↗
read the original abstract

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-\epsilon}$ edges.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript studies color fault-tolerant (CFT) distance preservers where edges/vertices receive colors with each color appearing at most k times and a single color fault crashes all elements of that color. In the multi-source setting with source set S, it claims existence of a CFT preserver H with Õ(n^{2-1/(k+1)} ⋅ |S|^{1/(k+1)}) edges that preserves all S×V distances under any single color fault; this sparsity is worst-case optimal up to polylog factors. It further gives a combinatorial randomized algorithm constructing such an H in Õ(m ⋅ n^{1-1/(k+1)} ⋅ |S|^{1/(k+1)}) time that is conditionally optimal under the combinatorial BMM conjecture, with the time bound remaining optimal even under mild sparsification to m^{1-ε} edges.

Significance. If the central claims hold, the work closes longstanding gaps in fault-tolerant distance preservers by exploiting color-correlated failures to obtain tight sparsity and time bounds unavailable in the classical k-fault model. The matching lower bound and BMM-based conditional optimality, together with the combinatorial (non-algebraic) algorithm, constitute a strong contribution to the area.

major comments (2)
  1. [§4] §4 (Construction): the argument that the single-color fault model plus per-color multiplicity k yields the precise exponent 2-1/(k+1) must be checked against the classical k-fault lower bounds; the manuscript should explicitly isolate the step where color correlation is used to beat the known gaps.
  2. [Theorem 6.1] Theorem 6.1 (Conditional lower bound): the reduction from combinatorial BMM to the preserver problem (including the mild-sparsification variant) needs to be verified for tightness; any hidden polylog factors or restrictions on k should be stated explicitly so the conditional optimality claim can be assessed.
minor comments (2)
  1. [Abstract] The abstract and introduction use Õ without a forward reference to the precise definition (including the dependence on k); add a short notation paragraph in the preliminaries.
  2. Figure 1 (or the illustrative example) would benefit from an explicit caption stating the color multiplicity and the single-color fault being preserved.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for recommending minor revision. We address the two major comments below and will incorporate the requested clarifications into the revised version.

read point-by-point responses

  1. Referee: [§4] §4 (Construction): the argument that the single-color fault model plus per-color multiplicity k yields the precise exponent 2-1/(k+1) must be checked against the classical k-fault lower bounds; the manuscript should explicitly isolate the step where color correlation is used to beat the known gaps.

    Authors: We appreciate the suggestion to make the distinction clearer. In the revised manuscript we will add a short dedicated paragraph at the beginning of §4 that contrasts the CFT model with the classical k-fault model. The key step that exploits color correlation is the following: because each color appears at most k times, a single color fault removes at most k edges/vertices, and the failure events are partitioned into color classes. This permits a generalized sampling argument in which we sample O(n^{1-1/(k+1)} |S|^{1/(k+1)}) vertices per color class and take the union over all colors; the union bound is taken over the (much smaller) number of colors rather than over all possible k-subsets of edges. In the classical model, where any k failures may occur independently, the corresponding union bound forces a weaker exponent. We will explicitly flag this sampling-and-union-bound step as the place where the color correlation is used. revision: yes

  2. Referee: [Theorem 6.1] Theorem 6.1 (Conditional lower bound): the reduction from combinatorial BMM to the preserver problem (including the mild-sparsification variant) needs to be verified for tightness; any hidden polylog factors or restrictions on k should be stated explicitly so the conditional optimality claim can be assessed.

    Authors: We agree that an explicit statement of the reduction parameters will help readers assess the claim. The proof of Theorem 6.1 gives a direct combinatorial reduction from n×n combinatorial BMM that produces a CFT-preserver instance with |S| = Θ(n^{1/(k+1)}) and m = Θ(n^2) (or m = n^{1+δ} for the mild-sparsification variant). The reduction introduces only polylogarithmic factors that are already absorbed by the Õ notation in both the upper and lower bounds; no additional polylog factors appear in the exponent. The argument holds for every fixed integer k ≥ 1 with no further restrictions. In the revised manuscript we will add a short remark immediately after the statement of Theorem 6.1 that records these parameters and confirms that the mild-sparsification case follows by applying the same reduction to a graph that has already been sparsified to m = n^{1+δ} edges. revision: yes

Circularity Check

0 steps flagged

No significant circularity; results are explicit constructions against external conjecture

full rationale

The paper defines the CFT model (single-color faults with per-color multiplicity at most k) as an external input and derives an explicit combinatorial construction for the Õ(n^{2-1/(k+1)} |S|^{1/(k+1)}) preserver together with a matching lower bound and BMM-based conditional time optimality. No equation or claim reduces by construction to a fitted parameter, self-definition, or self-citation chain; the sparsity and runtime bounds are obtained directly from the correlated-failure structure and are shown optimal within that model against an independent conjecture. Self-citations, if present for prior CFT work, are not load-bearing for the central sparsity or optimality statements.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the definition of the color fault model and standard undirected-graph assumptions; no free parameters are fitted and no new entities are postulated.

axioms (1)
  • domain assumption Each color appears at most k times on the edges or vertices of G.
    This multiplicity bound is the defining feature of the color fault model stated in the abstract.

pith-pipeline@v0.9.0 · 5960 in / 1357 out tokens · 62296 ms · 2026-05-22T17:49:05.864616+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Restora- tion by path concatenation: fast recovery of MPLS paths

    Yehuda Afek, Anat Bremler-Barr, Haim Kaplan, Edith Cohen, and Michael Merritt. Restora- tion by path concatenation: fast recovery of MPLS paths. Distributed Comput., 15(4):273–283, 2002

    work page 2002

  2. [2]

    Fault-Tolerant Bounded Flow Preservers

    Shivam Bansal, Keerti Choudhary, Harkirat Dhanoa, and Harsh Wardhan. Fault-Tolerant Bounded Flow Preservers. In 35th International Symposium on Algorithms and Computation (ISAAC 2024), volume 322 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:14, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik

    work page 2024

  3. [3]

    Fault tolerant reachability for di- rected graphs

    Surender Baswana, Keerti Choudhary, and Liam Roditty. Fault tolerant reachability for di- rected graphs. In Distributed Computing, pages 528–543, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg

    work page 2015

  4. [4]

    Fault-tolerant subgraph for single- source reachability: General and optimal

    Surender Baswana, Keerti Choudhary, and Liam Roditty. Fault-tolerant subgraph for single- source reachability: General and optimal. SIAM J. Comput. , 47(1):80–95, 2018

    work page 2018

  5. [5]

    Partially optimal edge fault-tolerant span- ners

    Greg Bodwin, Michael Dinitz, and Caleb Robelle. Partially optimal edge fault-tolerant span- ners. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 3272–3286. SIAM, 2022

    work page 2022

  6. [6]

    Preserving distances in very faulty graphs

    Greg Bodwin, Fabrizio Grandoni, Merav Parter, and Virginia Vassilevska Williams. Preserving distances in very faulty graphs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland , volume 80 of LIPIcs, pages 73:1–73:14. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2017

    work page 2017

  7. [7]

    Restorable shortest path tiebreaking for edge-faulty graphs

    Greg Bodwin and Merav Parter. Restorable shortest path tiebreaking for edge-faulty graphs. J. ACM, 70(5):28:1–28:24, 2023

    work page 2023

  8. [8]

    Better distance preservers and additive span- ners

    Greg Bodwin and Virginia Vassilevska Williams. Better distance preservers and additive span- ners. ACM Trans. Algorithms, 17(4):36:1–36:24, 2021

    work page 2021

  9. [9]

    Sparse sourcewise and pairwise distance preservers

    Don Coppersmith and Michael Elkin. Sparse sourcewise and pairwise distance preservers. SIAM J. Discret. Math. , 20(2):463–501, 2006

    work page 2006

  10. [10]

    Shared risk resource group complexity and approximability issues

    David Coudert, Pallab Datta, Stephane Perennes, Herv´ e Rivano, and Marie-Emilie Voge. Shared risk resource group complexity and approximability issues. Parallel Process. Lett. , 17(2):169–184, 2007

    work page 2007

  11. [11]

    Oracles for distances avoiding a failed node or link

    Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury, and Vijaya Ramachandran. Oracles for distances avoiding a failed node or link. SIAM J. Comput. , 37(5):1299–1318, 2008

    work page 2008

  12. [12]

    Karger, and Debmalya Panigrahi

    Mohsen Ghaffari, David R. Karger, and Debmalya Panigrahi. Random contractions and sam- pling for hypergraph and hedge connectivity. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 1101–1114. SIAM, 2017

    work page 2017

  13. [13]

    Multiple source dual fault tolerant BFS trees

    Manoj Gupta and Shahbaz Khan. Multiple source dual fault tolerant BFS trees. In 44th Inter- national Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland , volume 80 of LIPIcs, pages 127:1–127:15. Schloss Dagstuhl - Leibniz- Zentrum f¨ ur Informatik, 2017. 18

    work page 2017

  14. [14]

    Lima, Tom´ as Masar´ ık, Marcin Pilipczuk, and U´ everton S

    Lars Jaffke, Paloma T. Lima, Tom´ as Masar´ ık, Marcin Pilipczuk, and U´ everton S. Souza. A tight quasi-polynomial bound for global label min-cut. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 290–303. SIAM, 2023

    work page 2023

  15. [15]

    A brief note on single source fault tolerant reachability, 2019

    Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. A brief note on single source fault tolerant reachability, 2019

    work page 2019

  16. [16]

    A linear-time algorithm for finding a sparse k- connected spanning subgraph of a k-connected graph

    Hiroshi Nagamochi and Toshihide Ibaraki. A linear-time algorithm for finding a sparse k- connected spanning subgraph of a k-connected graph. Algorithmica, 7(5&6):583–596, 1992

    work page 1992

  17. [17]

    Dual failure resilient BFS structure

    Merav Parter. Dual failure resilient BFS structure. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebasti´ an, Spain, July 21 - 23, 2015 , pages 481–490. ACM, 2015

    work page 2015

  18. [18]

    Distributed constructions of dual-failure fault-tolerant distance preservers

    Merav Parter. Distributed constructions of dual-failure fault-tolerant distance preservers. In 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference , volume 179 of LIPIcs, pages 21:1–21:17. Schloss Dagstuhl - Leibniz- Zentrum f¨ ur Informatik, 2020

    work page 2020

  19. [19]

    Sparse fault-tolerant BFS trees

    Merav Parter and David Peleg. Sparse fault-tolerant BFS trees. In Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, volume 8125 of Lecture Notes in Computer Science , pages 779–790. Springer, 2013

    work page 2013

  20. [20]

    Sparse fault-tolerant BFS structures

    Merav Parter and David Peleg. Sparse fault-tolerant BFS structures. ACM Trans. Algorithms, 13(1):11:1–11:24, 2016

    work page 2016

  21. [21]

    Color fault-tolerant spanners

    Asaf Petruschka, Shay Sapir, and Elad Tzalik. Color fault-tolerant spanners. In 15th Innova- tions in Theoretical Computer Science Conference (ITCS) , pages 88:1–88:17, 2024

    work page 2024

  22. [22]

    Connectivity Labeling in Faulty Colored Graphs

    Asaf Petruschka, Shay Spair, and Elad Tzalik. Connectivity Labeling in Faulty Colored Graphs. In 38th International Symposium on Distributed Computing (DISC 2024) , volume 319 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 36:1–36:22, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik

    work page 2024

  23. [23]

    Efficient algorithms for the label cut problems

    Peng Zhang. Efficient algorithms for the label cut problems. In Theory and Applications of Models of Computation - 11th Annual Conference, TAMC , volume 8402 of Lecture Notes in Computer Science, pages 259–270. Springer, 2014

    work page 2014

  24. [24]

    The label cut problem with respect to path length and label frequency

    Peng Zhang and Bin Fu. The label cut problem with respect to path length and label frequency. Theor. Comput. Sci. , 648:72–83, 2016

    work page 2016

  25. [25]

    Simpler and better approximation algorithms for the unweighted minimum label s-t cut problem

    Peng Zhang, Bin Fu, and Linqing Tang. Simpler and better approximation algorithms for the unweighted minimum label s-t cut problem. Algorithmica, 80(1):398–409, 2018

    work page 2018

  26. [26]

    brute-force

    Peng Zhang and Linqing Tang. Minimum label s-t cut has large integrality gaps. Inf. Comput., 275:104543, 2020. A Single-Source Bounded Flow Preservers In this section we prove Theorem 1.7 regarding bounded flow preservers. We first give the formal and explicit definition: 19 Definition A.1 (E/CFT Single-Source Bounded Flow Preservers) . Let G = (V, E) be ...

    work page 2020