In parameterized complexity, structural graph parameters like treewidth, pathwidth, and treedepth act as a silver bullet for taming NP-hard problems. If a graph is "tree-like," global optimization problems can typically be broken down into localized choices via dynamic programming. This yields Fixed-Parameter Tractable (FPT) algorithms that run in time $f(k) \cdot n^{O(1)}$, confining the exponential runtime explosion entirely to the structural parameter $k$.
However, network routing and path-finding problems stubbornly resist this structural magic. Instead of becoming simple on restricted topologies, problems like finding disjoint paths or tracking constrained paths frequently remain $W[1]$-hard or even para-NP-hard. Understanding why these problems defy structural parameters requires looking at the fundamental conflict between local graph decompositions and the global nature of routing.
Why Routing Defies Local Structure
To see why structural parameters fail, consider the classic Edge-Disjoint Paths (EDP) problem. Given a graph and a set of terminal pairs $(s_i, t_i)$, the goal is to find paths connecting each pair such that no two paths share an edge.
In a standard tree decomposition, a hard problem like Vertex Cover or Independent Set can be solved because a vertex's validity depends only on its immediate neighbors. Once you fix the state of a small vertex separator (a "bag" in the tree decomposition), the components on either side become completely independent.
Routing, however, is inherently non-local. A path connecting $s_i$ to $t_i$ must traverse multiple bags, leaving a global "footprint" across the decomposition. It is not enough to know how many paths cross a separator; an algorithm must track which specific paths are connected to which distant terminals. This creates a massive coordination bottleneck.
As a result, the parameter inevitably forces its way into the exponent of the graph size. As shown by Ganian et al. in The Power of Cut-Based Parameters for Computing Edge Disjoint Paths, EDP remains $W[1]$-hard even when parameterized by tree-cut width. This means that while the problem is solvable in polynomial time for a fixed width, the computational overhead scales poorly as the graph's edge-connectivity complexity grows, ruling out an efficient FPT algorithm.
[ Component A ] ----( Separator Bag )---- [ Component B ]
s1 ------------------------------------> t1 (Global dependency)
s2 <------------------------------------ t2 (Global dependency)
This non-local complexity persists even when we try to bake the routing demands directly into the graph's structure. One common technique is to analyze the "augmented graph"—the input graph plus artificial edges connecting each terminal pair $(s_i, t_i)$. If the augmented graph has low treewidth, it implies that the routing demands align cleanly with the graph's physical layout. Yet, even this restriction is insufficient. In On Structural Parameterizations of the Edge Disjoint Paths Problem, Sridharan et al. proved that parameterizing EDP by the treewidth or feedback vertex set of the augmented graph still results in $W[1]$-hardness. The authors extended this boundary in On Structural Parameterizations of the Edge Disjoint Paths Problem, demonstrating a fundamental complexity barrier that separates disjoint routing from related tasks like the multicut problem.
The Directed Graph Escalation
The coordination problem becomes significantly worse when edges have direction. Intuitively, one might expect directed acyclic graphs (DAGs) to be simpler because the absence of cycles prevents paths from looping back on themselves. However, the loss of symmetry in directed graphs actually eliminates the topological tools used to solve undirected routing.
In directed topologies, the exponent of the runtime depends directly on the number of paths. As noted by Giannopoulou et al. in Directed Tangle Tree-Decompositions and Applications, achieving fixed-parameter tractability remains an open challenge because the underlying routing problems are $W[1]$-hard even on highly restricted acyclic digraphs. To find a way forward, the authors had to relax the problem entirely, using directed tangle tree-decompositions to achieve a polynomial-time algorithm under a half-integral relaxation (where paths can share capacity up to a factor of a half).
Without such relaxations, the intractability of directed routing is remarkably stubborn. In Directed disjoint paths remains W[1]-hard on acyclic digraphs without large grid minors, Lorenz et al. demonstrated that finding multiple disjoint paths remains $W[1]$-hard on DAGs even when excluding large grid minors. They proved that this hardness is congestion-invariant: allowing a fixed amount of vertex or edge sharing does not make the problem parameterizedly tractable. Furthermore, they showed that structural parameters designed to measure path identifiability, such as low ear anonymity, still fail to break the $W[1]$-hardness barrier.
Even searching for a single path can trigger $W[1]$-hardness if the path must satisfy exact structural constraints across different network layers. For example, Fertin et al. evaluated this in Finding Supported Paths in Heterogeneous Networks. They showed that finding a path of an exact length $k$ that maps consistently between a directed network and an associated undirected network remains $W[1]$-hard, even when the directed graph is completely acyclic.
Para-NP-Hardness: When Constant Width Fails
The ultimate boundary of parameterized intractability is para-NP-hardness. When a problem is $W[1]$-hard, it means we cannot isolate the exponential growth to the parameter; however, the problem might still be solvable in polynomial time for a fixed, constant parameter value (e.g., $n^{O(k)}$). When a problem is para-NP-hard, it remains NP-hard even when the parameter is fixed to a small constant.
This means the structural parameter provides absolutely no algorithmic leverage for exact solutions.
Complexity Hierarchy for Fixed Parameters:
FPT --> Solvable in f(k) * n^O(1) (Best case)
W[1]-hard --> Solvable in n^O(k) (Slow for large k)
Para-NP-hard --> NP-hard even for k = O(1) (Intractable from the start)
A striking example of this occurs in topological graph layouts. The Crossing Number problem asks for the minimum number of edge crossings needed to draw a graph on a plane. In Crossing Number Is NP-Hard for Constant Path-Width (And Tree-Width), Khazaliya et al. settled a long-standing open question by proving that computing the crossing number is para-NP-hard. Specifically, they showed that the problem remains NP-hard for graphs with a constant path-width of 12 or a tree-width of 9. This result proves that these popular width metrics are fundamentally insufficient to simplify the global geometric constraints of edge crossings.
A similar barrier emerges when trying to enforce global fairness constraints on paths. In The structural complexity landscape of finding balance-fair shortest paths, Bentert et al. studied colored graphs where a path must distribute vertices of each color as equally as possible. The authors proved that several structural parameterizations of this balance-fair shortest path problem are para-NP-hard. Fixing the graph's structural parameters to small constants fails to bypass the underlying hardness because balancing colors requires keeping track of history across the entire path, destroying the locality needed for dynamic programming.
Alternative Paradigms: Bypassing the Bottleneck
Because exact parameterized algorithms are so frequently out of reach for routing, researchers have shifted toward alternative algorithmic strategies to bypass these hardness barriers.
Shifting to Approximation
When exact solutions are blocked by $W[1]$-hardness, structural parameters can instead be leveraged to build better approximation algorithms. For instance, finding exact node-disjoint paths is $W[1]$-hard even when parameterized by treedepth. In On Routing Disjoint Paths in Bounded Treewidth Graphs, Ene et al. pivoted away from exact computation. By doing so, they bypassed the intractability bottleneck and designed a polynomial-time approximation algorithm that dropped the approximation ratio from an exponential $O(r \cdot 3^r)$ down to a sleek, polynomial $O(r^3)$ based on the graph's treewidth.
Algebraic Filtering
Another approach replaces combinatorial tracking with algebraic properties. Finding a simple path of length $k$ is NP-complete because it generalizes the search for a Hamiltonian path, as noted by Hassidim et al. in Finding the Minimum-Weight k-Path. Counting these paths is even harder.
To circumvent this, Dell et al. introduced a framework called "Extensor-Coding" in Extensor-coding. Instead of using standard dynamic programming to remember which vertices a path has visited, they mapped vertices to elements in an exterior (Grassmann) algebra. In this algebra, multiplying an element by itself causes it to vanish ($x \cdot x = 0$). This algebraic property automatically cancels out any paths that reuse a vertex, providing a highly efficient randomized method to count simple $k$-paths without explicitly tracking path histories.
Isolating the Source of Hardness
Finally, tractability can occasionally be recovered by strictly isolating the source of non-locality. In Shortest odd paths in undirected graphs with conservative weight functions, Jüttner et al. explored the Shortest Odd Path problem under conservative weights. While parity constraints usually cause global tracking issues, the authors identified "islands of tractability." They proved that if the negative-weight edges are confined to a single connected tree structure, the problem can be solved efficiently. The exponential complexity only returns if those negative edges are allowed to fracture across multiple disjoint components throughout the graph.
Key Foundational Work
Finding Supported Paths in Heterogeneous Networks (2015) — contributed 1 concept elements to this direction.
On Routing Disjoint Paths in Bounded Treewidth Graphs (2015) — contributed 1 concept elements to this direction.
Finding the Minimum-Weight k-Path (2013) — contributed 1 concept elements to this direction.