Pathwidth
In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph,[1] and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a 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,[2] and the pathwidth is one less than the size of the largest set in such a decomposition.
[10] Path decomposition may also be used to measure the space complexity of dynamic programming algorithms on graphs of bounded treewidth.
[11] 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.
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.
For instance, the interval graph shown with its interval representation in the figure has a path decomposition with five nodes, corresponding to its five maximal cliques ABC, ACD, CDE, CDF, and FG; the maximum clique size is three and the width of this path decomposition is two.
As Kirousis & Papadimitriou (1985) show, the node searching number of a graph equals its interval thickness.
A maximal pathwidth-k graph must be either a k-path or a k-caterpillar, two special kinds of k-tree.
[14] Since path-decompositions are a special case of tree-decompositions, the pathwidth of any graph is greater than or equal to its treewidth.
[15] For similar reasons, the cutwidth is at most the pathwidth times the maximum degree of the vertices in a given graph.
A linear arrangement formed by recursively partitioning each of these two subforests, placing the separating vertices between them, has logarithmic vertex searching number.
[20] In any planar graph, the pathwidth is at most proportional to the square root of the number of vertices.
[21] One way to find a path-decomposition with this width is (similarly to the logarithmic-width path-decomposition of forests described above) to use the planar separator theorem to find a set of O(√n) vertices the removal of which separates the graph into two subgraphs of at most 2n⁄3 vertices each, and concatenate recursively-constructed path decompositions for each of these two subgraphs.
The same technique applies to any class of graphs for which a similar separator theorem holds.
[5] The best known worst-case time bounds for computing the pathwidth of arbitrary n-vertex graphs are of the form O(2nnc) for some constant c.[32] 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.
In the first phase, the assumption that the graph has pathwidth k is used to find a path-decomposition or tree-decomposition that is not optimal, but whose width can be bounded as a function of k. In the second phase, a dynamic programming algorithm is applied to this decomposition in order to find the optimal decomposition.
Bodlaender (1994) surveys the complexity of computing the pathwidth on various special classes of graphs.
Graph minors have a deep theory in which several important results involve pathwidth.
In one direction, this result is straightforward to prove: if X does not include at least one forest, then the X-minor-free graphs do not have bounded pathwidth.
[4] This theory, in which pathwidth is intimately connected to arbitrary minor-closed graph families, has important algorithmic applications.
For, if the vertex separation number of a topological ordering is at most w, the minimum vertex separation among all orderings can be no larger, so the undirected graph formed by ignoring the orientations of the DAG described above must have pathwidth at most w. It is possible to test whether this is the case, using the known fixed-parameter-tractable algorithms for pathwidth, and if so to find a path-decomposition for the undirected graph, in linear time given the assumption that w is a constant.
Due to the limited capacity of human short-term memory,[56] Kornai and Tuza argue that this graph must have bounded pathwidth (more specifically, they argue, pathwidth at most six), for otherwise humans would not be able to parse speech correctly.
[10] For instance, if a linear ordering of the vertices of an n-vertex graph G is given, with vertex separation number w, then it is possible to find the maximum independent set of G in time O(2w n).
For instance, combining this dynamic programming approach with the fact that cubic graphs have pathwidth n/6 + o(n) shows that, in a cubic graph, the maximum independent set can be constructed in time O(2n/6 + o(n)), faster than previous known methods.
