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

CREATORMatthias Bentert, Esra Ceylan-Kettler, Valentin Hübner, Stefan Schmid, Jiří Srba
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-03934

Browse the full library · About the Tower of Babel