Tree-decompositions of small pathwidth Original Research Article

Motivated by the desire to speed up dynamic programming algorithms for graphs of bounded treewidth, we initiate a study of the tradeoff between width and pathwidth of tree-decompositions. We therefore investigate the catwidth parameter image which is the minimum width of any tree-decomposition image of a graph G when the pathwidth image of the tree T is 1. The catwidth parameter lies between the treewidth and the pathwidth of the graph, image, and just as treewidth relates to chordal graphs and pathwidth relates to interval graphs, catwidth relates to what we call catval graphs. We introduce the notion of an extended asteroidal triple (XAT) and characterize catval graphs as the XAT-free chordal graphs. We provide alternative characterizations of these graphs, show that there are graph classes for which the various parameters differ by an arbitrary amount, and consider algorithms for computing catwidth.