# Problems that are NP but polynomial on graphs of bounded treewidth

I heard here that the Hamiltonian cycle problem is polynomial on graphs of bounded treewidth.

I am interested in examples/references to different problems which is essentially hard but having polynomial complexity on graphs of bounded treewidth.

There are probably thousands of examples; there's a short list at ISGCI; the Wikipedia article has plenty of links. Search for "bounded treewidth" and "parameterized complexity treewidth" for many, many more.

Essentially, the problems become easy on graphs of bounded treewidth because:

1. Although it's NP-complete to determine if a graph has treewidth at most $k$ [1], there is, for every $k$ a linear-time algorithm to compute a tree decomposition of any graph that does actually have treewidth $k$ [2].

2. Once you have the tree decomposition, you can solve many problems by dynamic programming.

A simple example, which doesn't even use dynamic programming, is the Clique problem. Any clique of a graph must be contained completely in some node of the tree decomposition. That means that a graph of treewidth $k$ can have no clique of size greater than $k+1$ and, to find a clique of size at most $k+1$, you just have to see if each node of the decomposition contains the clique you're looking for. That can be done in linear time if $k$ is a fixed constant, since you're just checking for cliques in $O(n)$ graphs that each have at most $k+1$ vertices.

For a more complicated example, suppose you want to know if a graph $G$ of treewidth 4 is 3-colourable. First, compute the tree decomposition. Each vertex of the tree corresponds to a subgraph of at most 5 vertices of $G$. For each leaf of the tree, compute by brute force all 3-colourings of the corresponding subgraphs. This is in polynomial time because there are at most $n$ leaves, each corresponds to a subgraph with at most 5 vertices and there are at most $3^5=243$ 3-colourings of any such subgraph. Now, for each vertex $v$ of the tree that's adjacent to a leaf, enumerate all the 3-colourings that are compatible with possible colourings of the leaves adjacent to $v$. (That is, the 3-colourings of the subgraph corresponding to $v$ that can be extended to a 3-colouring of the graph corresponding to $v$ and all its adjacent leaves.) At this point, you can forget about the colourings of the leaves, since everything you need to know about them is now encoded in the distance-1 vertices. Now, iterate up the tree. You can imagine doing something similar for Hamiltonian path, constructing a path through the whole tree by joining up paths in the subtrees; that's more complicated.

[1] Arnborg, Corneil, and Proskurowski, "Complexity of finding embeddings in a k-tree"., SIAM Journal on Matrix Analysis and Applications 8(2): 277–284, 1987. DOI.

[2] Bodlaender, "A linear time algorithm for finding tree-decompositions of small treewidth", SIAM Journal on Computing 25 (6): 1305–1317, 1996. DOI.

• this bounded treewidth is an assumption right? I mean it is not property exist in these problems – seteropere Dec 21 '13 at 6:26
• I'm not sure what you mean. For all of these problems, and for all $k$, there is a polytime algorithm that solves the problem on all graphs of treewidth at most $k$, but fails for graphs of treewidth $k+1$ or greater. All of these problems have "yes" instances of all treewidths. For example, there are Hamiltonian graphs of all treewidths bigger than 1 and even 2-colourable graphs of all possible treewidths (e.g., grids). – David Richerby Dec 21 '13 at 11:48
• Forgive my ignorance David but how we set up the value for $k$? – seteropere Dec 22 '13 at 7:18
• @seteropere The statement is true for every value of $k$. So, for example, if you find that all the graphs you need to work with have treewidth between 1 and 5, you use the algorithm for $k=5$. – David Richerby Dec 22 '13 at 10:15

Typically, for many "local problems" such as $\mathsf{Vertex Cover}$ or $\mathsf{IndependentSet}$ (meaning a solution can be verified by checking the neighborhood of each vertex), standard dynamic programming methods run in $c^{\textbf{tw}}|V|^{O(1)}$ time, where $\textbf{tw}$ is the treewidth of the input graph, and $c$ is some (small) constant. For many of these problems, we have matching upper and lower bounds for the running time of the optimal solution, assuming the so-called Strong Exponential Time Hypothesis (SETH).

In some sense, problems with some "global constraint" (like connectivity) appear harder. For such problems, the typical DP algorithm has to consider all the ways in which the solution can traverse the corresponding separator of the tree decomposition, that is $\Omega(s^s)$, where $s$ is the size of the separator. For more, you could look at the FOCS'11 paper of Cygan et al., arXiv version here. They consider Monte Carlo algorithms for problems with global constraints. There is subsequent work in this direction that investigates the "need" for randomness.

You could also have a look at Chapter 5 of Fomin, Fedor V., and Dieter Kratsch. Exact exponential algorithms. Springer, 2010.