BlockPulserScience and industry

Four Graph Structures Define the Limits of Resilient Network Routing

In reporting published on November 20, 2026, Quanta Magazine described a mathematical result that answers a long-standing question about network routing: when can local rules deliver a data packet despite any pattern of failed links, provided a path to its destination still exists?

This property is called perfect resilience. It does not mean a network can deliver packets when failures have severed every possible path. Rather, it asks whether routers can avoid trapping packets in loops whenever a path remains.

In a paper presented at the Symposium on Theory of Computing in June 2026, Stefan Schmid and Matthias Bentert of the Technical University of Berlin proved that exactly four minimal graph structures prevent perfect resilience under the model introduced in 2012. A network that contains none of these structures as a graph minor can be given routing rules that deliver packets despite link failures, as long as a route remains. Their result also provides a fast algorithm for finding those rules.

Four Graph Structures Define the Limits of Resilient Network Routing

The model deliberately limits what a router can know. It may choose where to send a packet based on the packet’s destination, the link on which it arrived, and which of its neighboring links have failed—but not on the packet’s full travel history or a network-wide update. A graph minor is a simpler structure obtained by deleting nodes or links, or merging connected nodes. Schmid and colleagues identified two obstructing minors in 2020; Bentert later found two more and proved the set was complete.

The proof settles the question within that model, not every practical routing problem. Because the four obstructions are relatively simple, many networks—particularly densely connected ones—may contain them. The routing rules also do not account for speed or congestion. Schmid and Bentert plan to investigate whether allowing packets to carry a short record of recently visited nodes could make perfect resilience possible in more networks; that remains an open question.