Subexponential Algorithms

When a problem is NP-hard, the conventional wisdom is that solving it exactly requires time that grows exponentially with the input size — something like $2^{n}$. With 100 cities in a travelling salesman tour, that's more operations than atoms in the universe. Case closed?

Not quite. NP-hardness is a worst-case verdict: it tells you about the hardest possible inputs, not every input. Some inputs carry hidden structure that makes the problem dramatically easier. The most striking example involves planar graphs — graphs that can be drawn on a flat plane with no edges crossing.

For planar graphs, a beautiful result called the Planar Separator Theorem (Lipton & Tarjan, 1979) shows that every such graph can be cut in half by removing only $O(\sqrt{n})$ vertices. That small cut unlocks a divide-and-conquer recursion where each level works on a graph roughly half the size. The result: running times like $2^{O(\sqrt{n})}$ for problems such as planar Vertex Cover and planar Travelling Salesman — not polynomial, but astronomically better than $2^{n}$.

A related tool is treewidth: a measure of how "tree-like" a graph is. Graphs with small treewidth admit dynamic programming over their tree structure, again achieving subexponential or even polynomial time on problems that are hard in general.

These techniques live in a rich landscape called Fixed-Parameter Tractability (FPT), where the exponential explosion is confined to a structural parameter rather than the raw input size.

The demo below builds a small planar graph and applies the separator theorem recursively. Watch how removing only $O(\sqrt{n})$ vertices at each level splits the graph — and see how the resulting search-space count compares to brute force.

<p class="hint">
  {{hint}}
</p>
<div class="controls">
  <label>{{size_label}}
    <select id="nSelect">
      <option value="16">16 (4×4)</option>
      <option value="36">36 (6×6)</option>
      <option value="64">64 (8×8)</option>
    </select>
  </label>
  <button id="btnSep" type="button">{{btn_apply}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<canvas id="canvas" width="420" height="180"></canvas>
<table class="cmp" id="cmp"></table>
<div class="log" id="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: .7rem; flex-wrap: wrap; margin-bottom: .6rem; }
label { font-size: .9rem; display: flex; align-items: center; gap: .35rem; }
select { font: 14px system-ui; padding: .2rem .4rem; border-radius: 5px; border: 1px solid #cdd9e3; cursor: pointer; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; border: 1px solid #d0d7de; border-radius: 8px;
         background: #f6f8fa; width: 100%; max-width: 420px; }
.cmp { width: 100%; border-collapse: collapse; margin: .55rem 0 .3rem; font-size: .88rem; }
.cmp th { background: #e8eef3; padding: .3rem .5rem; text-align: left; border: 1px solid #cdd9e3; }
.cmp td { padding: .28rem .5rem; border: 1px solid #d0d7de; }
.cmp .bad { color: #c92f3c; font-weight: 700; }
.cmp .good { color: #0a7d33; font-weight: 700; }
.log { font-size: .82rem; color: #555; min-height: 1.2em; margin-top: .3rem; }

// Code not found

Notice how the brute-force search space ($2^{n}$) explodes with graph size, while the subexponential bound ($2^{2 \cdot \sqrt{n}}$) grows far more slowly. For n = 64, brute force needs $2^{64}$ ≈ 1.8 × $10^{19}$ operations; the separator bound is only $2^{16}$ = 65,536 — a factor of ~2.8 × $10^{14}$ smaller. That is the power of exploiting planar structure.

How good is $2^{O(\sqrt{n})}$, really? Let's put it in context.

• Brute force on an NP-hard problem with n binary choices takes $2^{n}$ time — intractable even for n = 100.
• The Planar Separator Theorem (Lipton & Tarjan, 1979) states: every planar graph with n vertices has a separator of at most 2√(2n) vertices whose removal leaves two parts each of size at most 2n/3. Applying this recursively gives a divide-and-conquer tree of depth $O(\log n)$, and the separator at each level has size $O(\sqrt{n})$.
• For Planar Vertex Cover, this yields a $2^{O(\sqrt{n})} \cdot n^{O(1)}$ algorithm: enumerate over the separator, recurse into each piece, and combine. Similar bounds hold for planar Travelling Salesman, planar Independent Set, and dozens of other problems.
• Is this optimal? Largely yes. Under the Exponential Time Hypothesis (ETH) — the widely-believed conjecture that 3-SAT requires $2^{\Omega(n)}$ time — planar problems cannot be solved in $2^{o(\sqrt{n})}$ time either. The separator theorem gives essentially the right exponent for planar graphs.
• Treewidth generalizes this: a graph of treewidth tw can be processed by tree decomposition in time $2^{O(tw)} \cdot n$, which is polynomial when tw = $O(\log n)$. Planar graphs have treewidth $O(\sqrt{n})$, recovering the same bound.

The take-away: NP-hardness describes the general case. When structure is present — planarity, small treewidth, bounded genus — the exponent shrinks, sometimes dramatically. This is the core insight of parameterized complexity and the FPT world.

Graphs that arise naturally in the physical world tend to be nearly planar — roads don't cross arbitrarily, chips are etched on flat silicon, and protein interaction networks have bounded local structure. That makes subexponential algorithms practically relevant:

• Road networks and logistics: city road maps are nearly planar (overpasses create few crossings). Exact TSP solvers for road networks exploit this structure to find optimal routes far faster than generic $2^{n}$ methods.
• VLSI circuit layout: placing components on a chip and routing wires to minimize crossings is fundamentally a planar problem. Subexponential dynamic programming on treewidth underlies modern layout tools.
• Network design: minimum-cost connectivity problems on planar utility grids (power, water, pipelines) admit subexponential exact solutions.
• Computational biology: phylogenetic trees have treewidth 1 (they are trees), and many genome-assembly graphs have low treewidth, enabling polynomial algorithms for problems that are NP-hard on general graphs.
• Games and puzzles: many grid-based puzzles (minesweeper variants, logic puzzles on grids) are planar; their exact solving complexity is $2^{O(\sqrt{n})}$ rather than $2^{n}$ when exploiting the grid structure.

Understanding when a hard problem is structurally easy is the bridge between theoretical NP-hardness and practical solvability. The P vs NP question may remain open, but for planar inputs the answer is already known: exponentially better than the worst case.

The story of subexponential algorithms is a story about structure. NP-hardness is a worst-case label — it tells you that some inputs are hard, not that your input is. Planar graphs, graphs of bounded treewidth, and other structured families let us confine the exponential explosion to a structural parameter, turning $2^{n}$ into $2^{O(\sqrt{n})}$ or better.

The Planar Separator Theorem is elegant: remove a small balanced cut, recurse, combine. The treewidth framework is flexible: any graph that is tree-like can be solved by dynamic programming along its tree decomposition. Together, they represent one of the deepest lessons in algorithm design — exploit the structure the problem gives you.

So the next time you see an NP-hard problem, the first question to ask is not "how do I handle the worst case?" but "what structure does my input actually have?" The answer might collapse an astronomical search space into something genuinely tractable. It may not be P vs NP, but it is often enough.