14
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Cyriac Antony
    Jun 29, 2019 at 7:36
  • $\begingroup$ You could also use their java application to see the classes where treewidth decomposition is hard (or easy) $\endgroup$
    – Cyriac Antony
    Jun 29, 2019 at 7:38

1 Answer 1

Reset to default
18
$\begingroup$

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

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.

Improve this answer
$\endgroup$
14
  • $\begingroup$ 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? $\endgroup$
    – PsySp
    Mar 20, 2017 at 16:10
  • 1
    $\begingroup$ Take 2 vertices and connect them by (n-2)/3 paths with 3 vertices on each path. There are roughly $3^{n/3}$ pmcs. $\endgroup$
    – daniello
    Mar 20, 2017 at 18:09
  • 8
    $\begingroup$ Bodlaender and Thilikos [DAM 79 (1997) 45-61] showed that computing treewidth is NP-hard for graphs of maximum degree 9. $\endgroup$
    – Yota Otachi
    Mar 20, 2017 at 20:50
  • 2
    $\begingroup$ 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. $\endgroup$
    – vb le
    Mar 21, 2017 at 18:45
  • 2
    $\begingroup$ 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. $\endgroup$
    – Yixin Cao
    Mar 24, 2017 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.