Complexity of Perfect and Ideal Resilience Verification in Fast Re-Route Networks
Matthias Bentert, Esra Ceylan-Kettler, Valentin Hübner, Stefan Schmid, Jiří Srba · 2026
Read Complexity of Perfect and Ideal Resilience Verification in Fast Re-Route Networks by Matthias Bentert, Esra Ceylan-Kettler, Valentin Hübner, Stefan Schmid, Jiří Srba (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-03934.txt.
Description
Matthias Bentert and four co-authors study the computational difficulty of verifying fast re-route networks, systems that recover from link failures using pre-installed local rules at each router. A perfectly resilient network always delivers packets whenever source and destination remain physically connected after failures. Some networks cannot achieve that ideal, and surprisingly little was known about the algorithmic side of checking it.
The team's main result is negative. Even checking whether a given set of static re-routing rules guarantees perfect resilience is coNP-complete. In that class, counterexamples are the short certificates, not proofs. That hardness holds for the seemingly basic checking task itself. Network teams should therefore not expect a general fast checker; design methods must build resilience in by construction or accept partial automated checks.
Catalog record
| CREATOR | Matthias Bentert, Esra Ceylan-Kettler, Valentin Hübner, Stefan Schmid, Jiří Srba |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 50 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-03934