within a constant factor of each other in the remaining cases. In some classes of graphs, it has been proven that the pathwidth and treewidth are always equal to each other: this is true for cographs, permutation graphs, the complements of comparability graphs, and the comparability graphs of interval orders. In any cubic graph, or more generally any graph with maximum vertex degree three, the pathwidth is at most , where is the number of vertices in the graph. There exist cubic graphs with pathwidth , but it is not known how to reduce this gap between this lower bound and the upper bound. Computing path-decompositions It is NP-complete to determine whether the pathwidth of a given graph is at most , when is a variable given as part of the input. The best known worst-case time bounds for computing the pathwidth of arbitrary -vertex graphs are of the form for some constant . 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. Fixed-parameter tractability Pathwidth is fixed-parameter tractable: for any constant , it is possible to test whether the pathwidth is at most , and if so to find a path-decomposition of width , in linear time. In general, these algorithms operate in two phases. In the first phase, the assumption that the graph has pathwidth is used to find a path-decomposition or tree-decomposition that is not optimal, but whose width can be bounded as a function of . In the second phase, a dynamic programming algorithm is applied to this decomposition in order to find the optimal decomposition. However, the time bounds for known algorithms of this type are exponential in , impractical except for the smallest values of . For the case an explicit linear-time algorithm based on a structural decomposition of pathwidth-2 graphs is given by . Special classes of graphs surveys the complexity of computing the pathwidth on various special classes of graphs. Determining whether the pathwidth of a graph is at most remains NP-complete when is restricted to bounded-degree graphs, planar graphs, planar graphs of bounded degree, chordal graphs, chordal dominoes, the complements of comparability graphs, and bipartite distance-hereditary graphs. It follows immediately that it is also NP-complete for the graph families that contain the bipartite distance-hereditary graphs, including the bipartite graphs, chordal bipartite graphs, distance-hereditary graphs, and