In graph theory, we often assume that if a graph is "thin"—meaning it looks somewhat like a tree—hard problems should become easy. This intuition is usually formalized through treewidth, a measure of how closely a graph resembles a tree. For decades, treewidth has been the gold standard for tractability: if you can bound the treewidth, you can usually solve NP-hard problems in polynomial time.
However, a growing body of research shows that for problems involving edges—like routing paths that cannot share an edge or drawing a graph with minimal crossings—treewidth is a "false friend." Even when a graph is incredibly thin by vertex standards, these edge-centric problems remain stubbornly difficult. To solve them, researchers are shifting their focus from vertex-based separators to cut-based structural parameters.
The Failure of Vertex Sparsity
The core of the issue lies in the difference between vertex-disjoint and edge-disjoint constraints. In vertex-disjoint paths (VDP), we care about bottlenecks at the nodes. Treewidth is perfect for this because it measures the size of vertex separators. But in the Edge-Disjoint Paths (EDP) problem, the bottlenecks are the edges.
As Robert Ganian and Sebastian Ordyniak demonstrate in The Power of Cut-Based Parameters for Computing Edge Disjoint Paths, EDP remains NP-hard even on graphs with very small treewidth or small vertex covers. This suggests that "sparsity" in terms of vertices does not translate to "simplicity" in terms of edge routing.
This phenomenon isn't limited to routing. Liana Khazaliya and Petr Hlinený recently settled a long-standing question in Crossing Number Is NP-Hard for Constant Path-Width (And Tree-Width), proving that calculating the minimum number of edge crossings is NP-hard even for graphs with a path-width of only 12. This result effectively precludes the existence of efficient algorithms based solely on these traditional width parameters.
Why Cut-Based Parameters Work
If vertex separators fail us, what works? The research points toward parameters that measure the complexity of edge cuts.
One such parameter is tree-cut width. While treewidth decomposes a graph based on vertex sets, tree-cut width looks at how the graph can be partitioned by cutting edges. In The Power of Cut-Based Parameters for Computing Edge Disjoint Paths, the authors show that while EDP is W[1]-hard (meaning it's unlikely to be fixed-parameter tractable), it is solvable in polynomial time if the tree-cut width is fixed. This identifies tree-cut width as the correct boundary for tractability where treewidth failed.
The intuition is that edge-disjoint problems are governed by the capacity of the "pipes" (edges) between different parts of the graph. A graph might have a very small treewidth but still possess a complex web of edges that makes routing impossible to optimize efficiently.
Mapping the Complexity Landscape
Researchers are now mapping exactly which parameters make these problems manageable. In On Structural Parameterizations of the Edge Disjoint Paths Problem, Robert Ganian, Sebastian Ordyniak, and M. S. Ramanujan identify the fracture number as a vital parameter. The fracture number measures how many vertices must be removed to break the graph into small, manageable components, providing a "silver lining" for achieving fixed-parameter tractability on augmented graphs.
This shift in perspective also applies to game theory and network flow. When agents behave selfishly in a network, we often look for a Nash Equilibrium. However, finding the socially optimal routing—the configuration that minimizes total congestion—is often much harder. Cornelius Brand and Fionn Mc Inerney show in The Complexity of Optimizing Atomic Congestion that this optimization is NP-hard even on simple networks. Again, the solution lies in edge-cut based parameters, which govern the computational difficulty of these system-wide optimizations.
Summary of the Shift
The transition from vertex-based to cut-based analysis represents a maturing understanding of graph complexity:
- Vertex-based measures (treewidth, path-width) are insufficient for problems where edges are the primary constraint.
- Edge-connectivity and cut-based parameters (tree-cut width, fracture number) provide a more accurate map of where routing problems become tractable.
- Structural parameters must match the "flavor" of the problem: edge-disjoint constraints require edge-based analysis.