# Are there interesting graph classes where the treewidth is hard (easy) to compute?

Treewith is an important graph parameter that indicates how close a graph is from being a tree (although not in a strict topological sense).

It is well known that computing the treewidth is NP-hard.

Are there any natural classes of graphs where the treewidth is hard to compute?

Similarly:

Are there interesting graph classes where the computation of the treewidth is easy? If yes, is there any structural property/test that can be exploited? I.e., Graph $G$ has property $X$ $\Rightarrow$ computing the treewidth of $G \in \mathbf{P}$.

• For graph classes where treewidth is bounded or unbounded, you can see graphclasses.org; search the parameter treewidth and you will get list of graph lasses where treewidth is bounded (or unbounded): graphclasses.org/classes/par_10.html Jun 29, 2019 at 7:36
• You could also use their java application to see the classes where treewidth decomposition is hard (or easy) Jun 29, 2019 at 7:38

Treewidth is NP-hard to compute on co-bipartite graphs, indeed the original NP-hardness proof of treewidth of Arnborg et al. shows this. Additionally, Bodlaender and Thilikos showed that it is NP-hard to compute the treewidth of graphs of maximum degree $9$. Finally, for any graph of treewidth at least $2$, subdividing an edge (i.e, replacing the edge by a degree $2$ vertex adjacent to the two edge endpoints) does not change the treeewidth of the graph. Hence it is NP-hard to compute treewidth of bipartite 2-degenerate graphs of arbitrarily large girth.
The problem is polynomial time solvable on chordal graphs, permutation graphs, and more generally on all classes of graphs with a polynomial number of potential maximal cliques, see this paper by Bouchitte and Todinca. Note that in the same paper it is shown that the set $\Pi(G)$ of potential maximal cliques of a graph $G$ can be computed from $G$ in time $O(|\Pi(G)|^2 \cdot n^{O(1)})$. Also, Bodlaender's algorithm determines whether $G$ has treewidth at most $k$ in time $2^{O(k^3)}n$. Hence, treewidth is polynomial time solvable for graphs of treewidth $O((\log n)^{1/3})$.
• Take 2 vertices and connect them by (n-2)/3 paths with 3 vertices on each path. There are roughly $3^{n/3}$ pmcs. Mar 20, 2017 at 18:09