cross-posted from: https://lemmy.ca/post/74182156
If a large outage cuts off every path between two points, there’s no way a packet can get through. But ideally, a network would be able to withstand any pattern of link failures short of this worst-case scenario. Researchers call this property “perfect resilience.” For over a decade, computer scientists have sought to understand what kinds of networks can be made perfectly resilient under realistic conditions.
Now, in a paper that was presented at the Symposium on Theory of Computing in June 2026, two researchers have settled the question (opens a new tab) with a comprehensive proof. They showed that there are exactly four minimal network structures that can thwart perfect resilience. In networks that lack these structures, you can always concoct rules that will reliably deliver packets from any source to any destination, regardless of which links fail.
“It’s a very elegant contribution,” said Michael Schapira (opens a new tab), a computer scientist at the Hebrew University of Jerusalem who was not involved in the result. “It’s pretty rare that you get a complete understanding of something.”
…
So now they had four forbidden graph structures. Were there more? Bentert tried the same strategy again: Prove that all graphs that lacked these four minors could be made perfectly resilient. The strategy worked, this time because he really had found the full set.
open access paper https://arxiv.org/abs/2006.06513

Figure 5: A rooted graph with two access nodes u and v (green). The skipping priority lists are depicted on the right. If s = v is the starting node and F = {u, t} (red link), then the resulting routing is (v, u, v, t) as in the first step πv(⊥, ∅) = u, then πu(v, {t}) = v, and finally πv(u, ∅) = t.

Figure 14: The four mentioned rooted graphs. Access nodes are green, fracture nodes are blue, and the red border shows the nodes in C.
We believe that our approach is versatile enough to also be used for these related problems. In particular, all of our preprocessing steps generalize directly to Perfect Resilience Synthesis with Source Matching. Additionally, it is already known that non-planar connected instances can be perfectly resilient if source matching is permitted. The forbidden rooted minors and the classes of rooted graphs that allow for perfectly resilient forwarding patterns thus change significantly in this setting and their characterization remains a practically and theoretically well motivated major open problem.
Our work also shows that skipping priority lists are as powerful as arbitrary forwarding functions in the context of perfect resilience. Whether this is also true in other contexts like ideal resilience remains an intriguing open problem. Also the question whether ideal resilience can always be achieved, that is, a k-link-connected graph is always resilient against k − 1 link failures, remains a major open problem. We note that our preprocessing step ensuring biconnectivity generalizes to ideal resilience and it can therefore be assumed that the input graph is 2-node-connected as well as k-link-connected. It would also be interesting to settle the complexity questions regarding ideal resilience. Even if ideal resilience can always be achieved, a proof of this fact might be non-constructive or only imply an exponential-time algorithm to compute an ideally resilient forwarding pattern.
researchers previous open access paper (elucidating the previous step this most recent research solved) https://arxiv.org/abs/2602.03827


