Pathwidth

In graph theory, a path decomposition of a graph G is, informally, a representation of G as a 'thickened' path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition isa sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition.Pathwidth is also known as interval thickness (one less than the maximum clique size in an interval supergraph of G), vertex separation number, or node searching number. In graph theory, a path decomposition of a graph G is, informally, a representation of G as a 'thickened' path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition isa sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition.Pathwidth is also known as interval thickness (one less than the maximum clique size in an interval supergraph of G), vertex separation number, or node searching number. Pathwidth and path-decompositions are closely analogous to treewidth and tree decompositions. They play a key role in the theory of graph minors: the families of graphs that are closed under graph minors and do not include all forests may be characterized as having bounded pathwidth, and the 'vortices' appearing in the general structure theory for minor-closed graph families have bounded pathwidth. Pathwidth, and graphs of bounded pathwidth, also have applications in VLSI design, graph drawing, and computational linguistics. It is NP-hard to find the pathwidth of arbitrary graphs, or even to approximate it accurately. However, the problem is fixed-parameter tractable: testing whether a graph has pathwidth k can be solved in an amount of time that depends linearly on the size of the graph but superexponentially on k. Additionally, for several special classes of graphs, such as trees, the pathwidth may be computed in polynomial time without dependence on k.Many problems in graph algorithms may be solved efficiently on graphs of bounded pathwidth, by using dynamic programming on a path-decomposition of the graph. Path decomposition may also be used to measure the space complexity of dynamic programming algorithms on graphs of bounded treewidth. In the first of their famous series of papers on graph minors, Neil Robertson and Paul Seymour (1983) define a path-decomposition of a graph G to be a sequence of subsets Xi of vertices of G, with two properties: The second of these two properties is equivalent to requiring that the subsets containing any particular vertex form a contiguous subsequence of the whole sequence. In the language of the later papers in Robertson and Seymour's graph minor series, a path-decomposition is a tree decomposition (X,T) in which the underlying tree T of the decomposition is a path graph. The width of a path-decomposition is defined in the same way as for tree-decompositions, as maxi |Xi| − 1, and the pathwidth of G is the minimum width of any path-decomposition of G. The subtraction of one from the size of Xi in this definition makes little difference in most applications of pathwidth, but is used to make the pathwidth of a path graph be equal to one. As Bodlaender (1998) describes, pathwidth can be characterized in many equivalent ways. A path decomposition can be described as a sequence of graphs Gi that are glued together by identifying pairs of vertices from consecutive graphs in the sequence, such that the result of performing all of these gluings is G. The graphs Gi may be taken as the induced subgraphs of the sets Xi in the first definition of path decompositions, with two vertices in successive induced subgraphs being glued together when they are induced by the same vertex in G, and in the other direction one may recover the sets Xi as the vertex sets of the graphs Gi. The width of the path decomposition is then one less than the maximum number of vertices in one of the graphs Gi. The pathwidth of any graph G is equal to one less than the smallest clique number of an interval graph that contains G as a subgraph. That is, for every path decomposition of G one can find an interval supergraph of G, and for every interval supergraph of G one can find a path decomposition of G, such that the width of the decomposition is one less than the clique number of the interval graph.