Finding the shortest path between two points is one of the most celebrated successes of network computer science. Algorithms like Dijkstra's solve this efficiently because they rely on the principle of optimality: an optimal path from $A$ to $C$ through $B$ must contain an optimal path from $A$ to $B$. This property allows algorithms to aggressively discard sub-optimal sub-paths, keeping the search space small and the execution time polynomial.
However, modern networks rarely care about distance alone. Whether routing data packets, financial transactions, or physical objects, paths must satisfy multiple independent constraints simultaneously—such as bandwidth limits, latency budgets, hop counts, and transaction fees. The moment these constraints are introduced, the principle of optimality shatters, transforming a simple pathfinding task into the Constrained Shortest-Path Problem, a class of problems that are frequently NP-complete or NP-hard.
Why Constraints Shatter Optimal Substructure
To understand why constraints break traditional pathfinding, consider a routing choice with two additive metrics: latency and cost. Suppose you want to find the lowest-latency path from node $A$ to node $C$ via node $B$, subject to a strict total cost budget of \$10.
There are two ways to get from $A$ to $B$:
- Path 1: Latency = 10ms, Cost = \$2
- Path 2: Latency = 5ms, Cost = \$9
If an algorithm behaves greedily, it will choose Path 2 because it offers the lowest latency to $B$. However, choosing Path 2 leaves only \$1 of the budget for the remaining journey from $B$ to $C$. If the only available path from $B$ to $C$ costs \$3, Path 2 becomes a dead end. To find a globally valid path, the algorithm would have been forced to choose Path 1—the locally sub-optimal sub-path—because it preserved enough budget to satisfy the remaining constraints.
Because sub-optimal sub-paths can no longer be safely discarded, algorithms must track the remaining budget for every constraint at every step. As shown by Sindura Saraswathi in An Exposition of Pathfinding Strategies Within Lightning Network Clients, adding constraints like maximum fees or minimum success probabilities forces routing clients to navigate an NP-complete landscape, often causing production implementations to rely on greedy heuristics that fail to find mathematically optimal routes.
The Mathematical Anatomy of Hardness
Not all constraints complicate routing in the same way. The computational complexity depends heavily on how metrics combine across links and how network layers interact.
Additive vs. Concave Metrics
Hong You and Guangjun Li point out in Routing algorithms with constrained bandwidth in service overlay networks based on Kautz graphs that optimizing for a single concave metric like bandwidth is computationally manageable. The bandwidth of a path is simply the minimum bandwidth of any single link along that path (the bottleneck). You can easily prune invalid links before running a shortest-path algorithm. However, when you combine a concave metric with additive metrics (like latency or hop counts), the problem quickly becomes intractable.
The Multi-Layer Protocol Trap
This complexity compounds in multi-layer networks, where data packets are encapsulated across different protocols (e.g., Ethernet inside IP inside MPLS). In a series of papers, including Path computation in multi-layer networks: Complexity and algorithms and Algorithmic and Complexity Aspects of Path Computation in Multi-Layer Networks, Mohamed Lamine Lamali et al. demonstrate that while basic multi-layer pathfinding is polynomial, adding a simple bandwidth constraint renders it NP-complete.
This shift occurs because the protocol stack state must be tracked alongside resource availability. The bandwidth constraint limits link traversals, forcing an exponential exploration of path segments to guarantee optimality. The authors proved that this hardness persists even under highly simplified conditions, such as on symmetric directed graphs containing only two distinct protocols.
The Backtracking Paradox
Constraints can also turn otherwise simple graph properties upside down. In The complexity of routing with collision avoidance, Till Fluschnik et al. study the problem of routing multiple objects without collisions. They show that finding collision-avoiding paths is NP-complete, but allowing arbitrary backtracking (walks) makes the problem solvable in polynomial time because objects have the freedom to wait or detour. However, the moment a maximum route length constraint is imposed, that tractability vanishes instantly. Restricting how long an object can wait or detour removes the mathematical freedom of backtracking, shifting the problem back to NP-complete.
Algorithmic Escape Hatches
Because exact solutions to these multi-constrained problems suffer from exponential worst-case complexity, they cannot be deployed directly in real-time network management systems where states evolve rapidly, such as satellite constellations or smart grids (Emmanuel Rachelson et al. in Dynamic unsplittable flows with path-change penalties: New formulations and solution schemes for large instances; Husheng Li and Weiyi Zhang in QoS Routing in Smart Grid). Instead, researchers rely on three primary paradigms to find near-optimal paths.
Heuristic Relaxation
When multiple constraints must be met, a common approach is to systematically relax them to find a feasible path. In End-to-End Network Delay Guarantees for Real-Time Systems Using SDN, Rakesh Kumar et al. address the multi-constrained path (MCP) problem for delay and bandwidth by relaxing one constraint at a time to isolate a valid path through Software-Defined Networks. Similarly, Gang Cheng and Nirwan Ansari designed the Bk-EB algorithm in Finding a least hop(s) path subject to multiple additive constraints to maximize the success rate of finding paths that satisfy multiple Quality of Service (QoS) requirements while explicitly minimizing the total hop count.
Alternative State Spaces
Instead of searching through individual paths directly, some frameworks alter the underlying decision variables. Pham Quang Dung et al. demonstrate in A Local Search Modeling for Constrained Optimum Paths Problems (Extended Abstract) that using rooted spanning trees as the core decision variable in a local search framework allows algorithms to navigate highly constrained search spaces more effectively than traditional greedy path mutations, outperforming standard metaheuristics.
Neural Imitation
When a network requires real-time routing decisions but the underlying optimization problem is an NP-hard multicommodity flow problem, machine learning can bypass the computational bottleneck. In NeuRoute: Predictive Dynamic Routing for Software-Defined Networks, Abdelhadi Azzouni et al. introduce a framework that trains a neural network to imitate a mathematically sound but slow routing heuristic. By learning the underlying patterns of the heuristic, the neural network predicts near-optimal routing paths in a fraction of the time, allowing networks to proactively adapt to congestion without running expensive optimization routines online.
Key Foundational Work
Optical grid networks (2007) — contributed 1 concept elements to this direction.
Finding a least hop(s) path subject to multiple additive constraints (2006) — contributed 1 concept elements to this direction.