Calculating a backup path after two network failures is mathematically no harder than calculating one after a single failure.
Graph theorists have long assumed that every additional failure in a network makes finding a new path exponentially more complex. This research provides a tight reduction that proves this intuition wrong for undirected graphs. The 2-Fault problem is actually equivalent in difficulty to the 1-Fault version. This simplifies how we design resilient infrastructure like power grids or internet routing protocols. It means we can build more reliable systems without the massive computational overhead we thought was required.
Undirected Replacement Paths: Dual Fault Reduces to Single Source
arXiv · 2605.02114
Given a graph and two fixed vertices $s$ and $t$, the Replacement Path Problem (RP) is to compute for every edge $e$, the distance between $s$ and $t$ when $e$ is removed. There are two natural extensions to RP: (1) Single Source Replacement Paths (SSRP): Given a graph $G$ and a source node $s$, compute for every vertex $v$ and every edge $e$ the $s$-$v$ distance in $G \setminus \{e\}$. That is, we do not fix the target anymore. (2) $2$-Fault Replacement Paths (2-FRP): Given a graph $G$ and two