[Solved]: Problems that are NP but polynomial on graphs of bounded treewidth

Problem Detail: 

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.

Asked By : seteropere

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19019