Finding the shortest path between two points in a graph is one of the most fundamental, easily solvable problems in computer science. Algorithms like Dijkstra's or Bellman-Ford find optimal paths in polynomial time because they exploit an optimal substructure: the shortest path from $A$ to $C$ via $B$ contains the shortest path from $A$ to $B$.
However, real-world networks rarely operate under such simple, isolated conditions. When we introduce capacity constraints, hardware limitations, multi-destination requirements, or stateful rebalancing, routing decisions become globally coupled. Choosing a path for one packet changes the topology or resource availability for the next. This coupling destroys the optimal substructure, rapidly transforming trivial routing tasks into computationally intractable NP-hard or NP-complete optimization problems.
The Dichotomy of Constraints
Why does adding a single real-world constraint make routing so difficult? The answer often depends on the underlying network topology and how traffic is forced to interact with it.
Consider node-constrained traffic engineering, where traffic must pass through specific intermediate "middlepoints" (such as firewalls or proxies) before reaching its final destination. Trimponias et al. demonstrated a striking computational dichotomy in this space: if the network graph is undirected, the problem can be solved efficiently in polynomial time. However, the moment the network contains directed edges—a necessity for modeling real-world telecommunications—the problem becomes strictly NP-hard.
Undirected Network: Polynomial Time (Tractable)
[Source] --- (Middlepoint) --- [Destination]
Directed Network: NP-hard (Intractable)
[Source] --> (Middlepoint) --> [Destination]
Similarly, intractability emerges when flows cannot be split across multiple paths. When non-splittable traffic must be routed through networks with embedded computational services (such as in-network data processing), balancing both traffic load and computational capacity becomes NP-hard, as shown by Mei et al..
Even when trying to simplify routing tables using structured rules like Interval Routing Schemes (IRS)—which assign contiguous intervals of destination addresses to specific output ports—minimizing network congestion remains fundamentally difficult. Cicerone et al. proved that designing an optimal IRS to minimize maximum link load is NP-complete, a hardness that persists even for simple one-to-all communication patterns.
Traffic Grooming and Sharp Structural Boundaries
In optical Wavelength Division Multiplexing (WDM) networks, a core challenge is traffic grooming: multiplexing low-speed traffic streams onto high-capacity wavelengths. The goal is to minimize the deployment of expensive electronic hardware, such as Add-Drop Multiplexers (ADMs). Xu et al. noted that this resource allocation problem is fundamentally NP-hard due to the combinatorial explosion of ways to group these streams.
What makes traffic grooming a fascinating case study in computational complexity is how quickly it becomes intractable, even when the network topology is stripped down to its simplest form:
- Chain Topologies: Shalom et al. proved that minimizing hardware costs via traffic grooming remains NP-complete even when the network is a simple linear chain and the grooming factor is small.
- Star Topologies: Shalom et al. mapped out a sharp mathematical boundary in star networks. When the grooming factor $C$ (the number of low-speed circuits that can share a single wavelength) is 2 or less, the problem can be solved optimally in polynomial time. However, for any grooming factor $C > 2$, the problem immediately transitions to being NP-complete.
Grooming Factor (C) ≤ 2 --> Polynomial Time (O(N^k))
Grooming Factor (C) > 2 --> NP-complete (Reduction from Edge Partitioning)
Stateful Networks and Rebalancing Intractability
Modern decentralized networks, such as blockchain-based Payment Channel Networks (PCNs) like the Lightning Network, introduce a dynamic layer of complexity: stateful channels. To route a transaction from user $A$ to user $C$ through intermediary $B$, the channel $A \to B$ must have sufficient local balance, and $B \to C$ must have sufficient remote balance. Transactions actively alter these balances, meaning the routing topology changes with every single event.
Varma et al. proved that executing exact throughput-optimal routing algorithms in these stateful environments is computationally intractable due to its NP-hard nature.
If a channel runs out of funds in one direction, it must be rebalanced by moving funds along a cycle. However, finding the optimal way to shift these funds to maximize overall transaction success rates is incredibly difficult. Ni et al. demonstrated that this utility-aware rebalancing problem is not only NP-hard but also inapproximable within a constant ratio. This means it is mathematically impossible for any polynomial-time algorithm to guarantee a solution within a fixed percentage of the absolute best possible outcome, forcing practitioners to rely entirely on local heuristics.
Path Selection vs. Transmission Scheduling
A recurring insight across this literature is the stark complexity gap between deciding when to send data (scheduling) and deciding where to send data (routing).
For example, in Gaussian half-duplex relay line networks, nodes cannot transmit and receive simultaneously on the same frequency. Ezzeldin et al. showed that if the path is already fixed as a straight line, finding the optimal transmission schedule is highly efficient, requiring only $O(N^2)$ time. However, the moment you expand the problem to find the optimal routing path within a general mesh network of half-duplex relays, the problem becomes NP-hard.
Fixed Path Routing --> Scheduling is Efficient (O(N²))
General Mesh Network --> Path Selection is NP-hard
A similar phenomenon occurs in green networking and energy harvesting. Diakonikolas et al. found that while calculating max-min fair data rates for a pre-defined route is computationally efficient, identifying the underlying routing topology that maximizes the minimum sensing rate across energy-harvesting nodes is NP-hard.
Reductions to Classical Hard Problems
Why do these diverse network problems all hit the same wall of intractability? Under the hood, adding constraints to routing problems implicitly forces them to solve classical NP-hard combinatorial problems, such as the Traveling Salesman Problem (TSP), the Stacker Crane Problem, or Knapsack variants.
- Multi-Goal Pathfinding: When a vehicle or packet must visit a specific subset of required locations in a graph before reaching its destination, Chour et al. noted that the problem directly inherits the NP-hardness of the TSP.
- Decentralized Learning Topologies: In distributed machine learning frameworks like GADMM, workers must be organized into a logical communication chain to minimize overhead. Elgabli et al. showed that finding this optimal communication sequence is computationally expensive because it directly mirrors the TSP.
- Dynamic Transportation Fleets: For routing physical delivery vehicles with explicit pickup and delivery constraints, Treleaven et al. highlighted that the underlying Stacker Crane Problem is fundamentally intractable for large request volumes, with standard approximations yielding poor worst-case guarantees.
- Energy and Resilience Optimization: Even when the objective is purely structural—such as turning off network links to save energy while maintaining traffic demands (Mazauric et al.) or selecting bipartite subnetworks that are resilient against contagion spread (Heinecke et al.)—the problems reduce to hard combinatorial packing and partitioning challenges.
Coping with Intractability
Because these core traffic engineering and routing problems are fundamentally hard, the research community has shifted away from pursuing exact global optimums for large-scale networks. As Wang et al. observed in traditional OSPF routing networks, the computational burden of exact optimization necessitates a reliance on metaheuristics, approximation frameworks, and localized greedy algorithms. By understanding exactly where the boundary of tractability lies—whether it is a transition from undirected to directed graphs, or a grooming factor exceeding two—network designers can better choose when to look for exact solutions and when to settle for high-quality approximations.
Key Foundational Work
Static and dynamic low-congested interval routing schemes (2002) — contributed 5 concept elements to this direction.
Static and Dynamic Low-Congested Interval Routing Schemes (1998) — contributed 3 concept elements to this direction.
Route oscillations in I-BGP with route reflection (2002) — contributed 1 concept elements to this direction.