Computing Path-decompositions
It is NP-complete to determine whether the pathwidth of a given graph is at most k, when k is a variable given as part of the input. The best known worst-case time bounds for computing the pathwidth of arbitrary n-vertex graphs are of the form O(2n nc) for some constant c. Nevertheless several algorithms are known to compute path-decompositions more efficiently when the pathwidth is small, when the class of input graphs is limited, or approximately.
Read more about this topic: Path Decomposition