Graph problems that are NP-hard in general often become easy when the input graph looks "tree-like." This structural simplicity is formally measured by treewidth. Thanks to classic results like Courcelle's Theorem, if a graph property can be described in standard monadic second-order logic, we can solve it in time proportional to $f(tw) \cdot n$. This is known as Fixed-Parameter Tractability (FPT): the exponential explosion is entirely confined to the structural parameter ($tw$), leaving the input size ($n$) as a benign polynomial.
But what happens when a problem escapes this neat boundary? For many complex graph problems—particularly those involving geometric layouts, global paths, or metric distances—low treewidth only guarantees an XP (Slice-Wise Polynomial) algorithm, which runs in time like $n^{O(tw)}$.
To see why this creates a crisis in practice, consider a graph with one million nodes ($n = 10^6$) and a modest treewidth of $tw = 5$. An FPT algorithm might take $2^5 \cdot 10^6 \approx 3.2 \times 10^7$ operations—less than a second on a modern laptop. An XP algorithm, however, would take $(10^6)^5 = 10^{30}$ operations, which is completely intractable. This stark divide is known as the parameterized complexity gap.
The Limits of Treewidth
For years, researchers hoped that open problems in graph drawing and network routing would eventually yield efficient FPT algorithms under treewidth. Recent breakthroughs have shattered this optimism by mapping the exact boundaries of this gap.
Take Upward Planarity Testing, a foundational problem in graph visualization. While it was known to be solvable in polynomial time for fixed treewidth, Steven Chaplick et al. highlighted in Parameterized Algorithms for Upward Planarity the persistent gap between this XP classification and true FPT efficiency. This boundary was definitively resolved by Bart M. P. Jansen et al. in Upward and Orthogonal Planarity are W[1]-hard Parameterized by Treewidth, proving that testing for upward and rectilinear planarity is $W[1]$-hard when parameterized by treewidth. This means that the existing $n^{O(tw)}$ algorithms are likely the best we can ever achieve.
An even more dramatic manifestation of this gap occurs in the Crossing Number problem. One might expect that if a graph is nearly a tree, minimizing its edge crossings would be straightforward. However, in Crossing Number Is NP-Hard for Constant Path-Width (And Tree-Width), Liana Khazaliya et al. proved that computing the crossing number remains NP-hard even for graphs with a constant tree-width of 9 or path-width of 12. Here, the complexity gap doesn't just separate FPT from XP; it separates polynomial time from outright NP-hardness for fixed parameter values.
Why the Gap Exists: The Failure of Locality
To understand why some problems fall into the XP trap or remain NP-hard under low treewidth, we must look at how tree decompositions work.
A tree decomposition breaks a graph into small, overlapping clusters (called bags) arranged in a tree structure. Standard dynamic programming works locally: it computes solutions for a bag based solely on the solutions of its children, using the small vertex separator between them to decouple the rest of the graph. This works perfectly for problems like Independent Set, where a vertex's eligibility depends only on its immediate neighbors.
However, problems like upward planarity, crossing minimization, or finding a Geodetic Set (a minimum set of vertices whose shortest paths cover the graph) require global coordination. As Prafullkumar Tale demonstrates in Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number, metric-based problems are inherently non-local. A choice made in one bag can alter shortest paths or edge crossings across the entire graph.
To maintain valid global states during dynamic programming, an algorithm cannot just remember what happens inside the separator; it must track how vertices within a bag interact with the entire external graph topology. This forces the number of tracking states to depend on $n$, pushing the parameter into the exponent and creating the $n^{O(tw)}$ complexity gap.
Climbing the Parameter Hierarchy
When treewidth fails to deliver an FPT algorithm, how do we bridge the gap? The strategy is to climb to more restrictive structural parameters within the graph parameter hierarchy.
If a problem is $W[1]$-hard or NP-hard under treewidth, researchers restrict the input further by parameterizing by metrics like treedepth, feedback vertex set (FVS), or vertex cover number (VC).
[ Treewidth ] <-- Least restrictive (Hardest to get FPT)
▲
[ Pathwidth ]
▲
[ Treedepth ] / [ Feedback Vertex Set ]
▲
[ Vertex Cover Number ] <-- Most restrictive (Easiest to get FPT)
For example, while the path-saturation constraints in Clustered Planarity with Linear Saturators (CPLS) remain NP-hard even on trees (treewidth 1), Giordano Da Lozzo et al. bypassed this barrier in Exact Algorithms for Clustered Planarity with Linear Saturators by designing FPT algorithms using the vertex cover number.
Similarly, in layout problems like the Stack Layout Extension, Thomas Depian et al. showed in The Parameterized Complexity Of Extending Stack Layouts that bounding the number of pages alone leaves the problem intractable; one must also bound the "page width" to achieve fixed-parameter tractability.
By systematically mapping which parameters unlock FPT algorithms and which trap us in XP, this line of research clarifies exactly what kind of structural information is needed to tame globally constrained problems.
Key Foundational Work
On finding short resolution refutations and small unsatisfiable subsets (2006) — contributed 1 concept elements to this direction.