Problems that are NP but polynomial on graphs of bounded treewidth

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

Perhaps you could start with:

H. Bodlaender and A. Koster, Combinatorial Optimization on Graphs of Bounded Treewidth, The Computer Journal 51 (3), 255-269, 2008.

Found that reference under "Resources" from here.

Answer 4

Here is a recent study of this phenomenon of treewidth limiting the complexity of the problem and moving it into P from the point-of-view of SAT instance (hardness). This might underlie a larger framework to help understand the simplification across other NP-complete problems (via reductions to SAT).

Strong Backdoors to Bounded Treewidth SAT Gaspers/Szeider 2012

Decomposability can be considered in terms of the treewidth of a graph that is associated with the given CNF formula, for instance by considering clauses and variables as vertices of the graph, and making a variable adjacent with all the clauses it appears in. On the other hand, a strong backdoor set of a CNF formula is a set of variables such that each possible partial assignment to this set moves the formula into a fixed class for which (#)SAT can be solved in polynomial time. In this paper we combine the two above approaches. In particular, we study the algorithmic question of finding a small strong backdoor set into the class W_t of CNF formulas whose associated graphs have treewidth at most t.