<p>Treewidth is NP-hard to compute on co-bipartite graphs, indeed <a href="http://epubs.siam.org/doi/10.1137/0608024" rel="noreferrer">the original NP-hardness proof of treewidth</a> of Arnborg et al. shows this. Additionally, <a href="http://www.sciencedirect.com/science/article/pii/S0166218X97000310?via%3Dihub" rel="noreferrer">Bodlaender and Thilikos</a> 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$, <em>subdividing</em> 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.</p>

<p>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 <a href="http://epubs.siam.org/doi/10.1137/S0097539799359683" rel="noreferrer">this paper</a> 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, <a href="http://epubs.siam.org/doi/10.1137/S0097539793251219" rel="noreferrer">Bodlaender's algorithm</a> 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})$.</p>

<p>It is an outstanding open problem whether computing the treewidth of planar graphs is polynomial time solvable or NP complete. It is worth noting that the related graph parameter branchwidth (which is always within a factor 1.5 away from treewidth) is <a href="http://link.springer.com/article/10.1007/BF01215352" rel="noreferrer">polynomial time computable on planar graphs.</a></p>

CC BY-SA 3.0
2017-03-20T16:10:21.697Z
Thank you. So the only class known to be hard is co-bipartite graphs? The property of potential maximal cliques does not seem surprising to me. Is this property P-time testable?
PsySp
CC BY-SA 3.0
2017-03-20T16:46:15.987Z
Co-bipartite graphs is the only minimal class that i know of, but there might be more.
daniello
CC BY-SA 3.0
2017-03-20T16:47:26.947Z
Is anything known about regular/bounded degree graphs besides the fact that treewidth can be unbounded? I will probably add it to my question.
PsySp
CC BY-SA 3.0
2017-03-20T16:53:16.373Z
I'm not aware of anything concrete on bounded degree graphs.
daniello
CC BY-SA 3.0
2017-03-20T16:55:35.020Z
Thank you so much for your time to answer. It is fascinating to me (an outlier on treewidth stuff) that so little is known.
PsySp
CC BY-SA 3.0
2017-03-20T16:59:53.223Z
Indeed, if a more thorough literature search reveals that hardness for bounded degree is not known, this should be fixed by someone :)
daniello
CC BY-SA 3.0
2017-03-20T17:19:13.347Z
Are there any known families of planar graphs for which the number of potential maximal cliques is exponentially large?
Gamow
CC BY-SA 3.0
2017-03-20T18:09:08.367Z
Take 2 vertices and connect them by (n-2)/3 paths with 3 vertices on each path. There are roughly $3^{n/3}$ pmcs.
daniello
CC BY-SA 3.0
2017-03-20T20:50:11.510Z
Bodlaender and Thilikos [DAM 79 (1997) 45-61] showed that computing treewidth is NP-hard for graphs of maximum degree 9.
Yota Otachi
CC BY-SA 3.0
2017-03-21T18:45:31.497Z
In addition to the hardness for co-bipartite graphs, it should also be mentioned that computing treewidth is also hard for bipartite graphs, first observed, I think, by Ton Kloks in his PhD thesis.
vb le
CC BY-SA 3.0
2017-03-21T22:06:23.680Z
Added :), and I added a link to Bodlaender's algorithm as well. Perhaps this answer is approaching a community wiki?
daniello
CC BY-SA 3.0
2017-03-23T20:35:22.287Z
It's possibly worth adding that although treewidth for planar graphs is open, branchwidth (which is always within a constant factor of treewidth) can be computed exactly for planar graphs in polynomial time.
David Eppstein
CC BY-SA 3.0
2017-03-24T11:06:57.460Z
You may mention that (almost) nothing is known about its approximation complexity and parameterized lower bounds. In principle, there may be PTAS or subexponential-time algorithm, though both very unlikely. The only approximation hardness is one based on the small set expansion (SSE).  doi:10.1613/jair.4030.
Yixin Cao
CC BY-SA 3.0
2017-03-25T16:22:45.663Z
I like the direction where this answer is going :)
PsySp
CC BY-SA 3.0
2017-03-20T16:01:05.437Z
2017-03-25T16:03:21.030Z
2017-03-25T16:03:21.030Z
daniello
<p>Treewith is an important graph parameter that indicates how close a graph is from being a tree (although not in a strict topological sense).</p>

<p>It is well known that computing the treewidth is NP-hard.</p>

<blockquote>
  <p>Are there any natural classes of graphs where the treewidth is <em>hard</em> to compute?</p>
</blockquote>

<p>Similarly:</p>

<blockquote>
  <p>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}$.</p>
</blockquote>

CC BY-SA 4.0
2019-06-29T07:36:48.210Z
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):  http://graphclasses.org/classes/par_10.html
Cyriac Antony
CC BY-SA 4.0
2019-06-29T07:38:28.423Z
You could also use their java application to see the classes where treewidth decomposition is hard (or easy)
Cyriac Antony
<graph-theory><np-hardness><polynomial-time><treewidth>
Are there interesting graph classes where the treewidth is hard (easy) to compute?
PsySp
# Are there interesting graph classes where the treewidth is hard (easy) to compute?

(Asked by: username_0 on 2017-03-20)

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}$.

**Tags:** graph-theory, np-hardness, polynomial-time, treewidth

> **Comments:**
> **username_1**: 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):  http://graphclasses.org/classes/par_10.html  
> **username_1**: You could also use their java application to see the classes where treewidth decomposition is hard (or easy)  

---

## 1 answers

### Answer by username_2 on 2017-03-20. Score: 18

Treewidth is NP-hard to compute on co-bipartite graphs, indeed [the original NP-hardness proof of treewidth](http://epubs.siam.org/doi/10.1137/0608024) of Arnborg et al. shows this. Additionally, [Bodlaender and Thilikos](http://www.sciencedirect.com/science/article/pii/S0166218X97000310?via%3Dihub) 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](http://epubs.siam.org/doi/10.1137/S0097539799359683) 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](http://epubs.siam.org/doi/10.1137/S0097539793251219) 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})$.

It is an outstanding open problem whether computing the treewidth of planar graphs is polynomial time solvable or NP complete. It is worth noting that the related graph parameter branchwidth (which is always within a factor 1.5 away from treewidth) is [polynomial time computable on planar graphs.](http://link.springer.com/article/10.1007/BF01215352)

> **Comments:**
> **username_0**: Thank you. So the only class known to be hard is co-bipartite graphs? The property of potential maximal cliques does not seem surprising to me. Is this property P-time testable?  
> **username_2**: Co-bipartite graphs is the only minimal class that i know of, but there might be more.  
> **username_0**: Is anything known about regular/bounded degree graphs besides the fact that treewidth can be unbounded? I will probably add it to my question.  
> **username_2**: I'm not aware of anything concrete on bounded degree graphs.  
> **username_0**: Thank you so much for your time to answer. It is fascinating to me (an outlier on treewidth stuff) that so little is known.  
> **username_2**: Indeed, if a more thorough literature search reveals that hardness for bounded degree is not known, this should be fixed by someone :)  
> **username_3**: Are there any known families of planar graphs for which the number of potential maximal cliques is exponentially large?  
> **username_2**: Take 2 vertices and connect them by (n-2)/3 paths with 3 vertices on each path. There are roughly $3^{n/3}$ pmcs.  
> **username_4**: Bodlaender and Thilikos [DAM 79 (1997) 45-61] showed that computing treewidth is NP-hard for graphs of maximum degree 9.  
> **username_5**: In addition to the hardness for co-bipartite graphs, it should also be mentioned that computing treewidth is also hard for bipartite graphs, first observed, I think, by Ton Kloks in his PhD thesis.  
> **username_2**: Added :), and I added a link to Bodlaender's algorithm as well. Perhaps this answer is approaching a community wiki?  
> **username_6**: It's possibly worth adding that although treewidth for planar graphs is open, branchwidth (which is always within a constant factor of treewidth) can be computed exactly for planar graphs in polynomial time.  
> **username_7**: You may mention that (almost) nothing is known about its approximation complexity and parameterized lower bounds. In principle, there may be PTAS or subexponential-time algorithm, though both very unlikely. The only approximation hardness is one based on the small set expansion (SSE).  doi:10.1613/jair.4030.  
> **username_0**: I like the direction where this answer is going :)  

---

