Finding the treewidth of a graph is an NPcomplete problem (Arnborg, Corneil, and Proskurowski 1987).
given a graph of n vertices and treewidth k, a simple algorithm finds the optimal tree decomposition in time O(n k+2 ) (Arnborg, Corneil, and Proskurowski 1987), and a variety of approximation algorithms and heuristics are known for the treewidth problem (Bodlaender et al.