TOPICS
Search

Pathwidth

The pathwidth of a graph G, also called the interval thickness, vertex separation number, and node searching number, is one less than the size of the largest set in a path decomposition G.

PathwidthForbiddenMinors

As summarized in the table below, obstruction sets for pathwidth <=1 (consisting of the triangle graph C_3 and spoke graph S(3,2), illustrated above) and <=2 (consisting of 110 graphs) were described in Kinnersley and Langston (1992) taking advantage of the fact that gate matrix layout with parameter k is identical to the pathwidth problem with parameter k-1 (Fellows and Langston 1989, Kinnersley and Langston 1992).

pathwidth boundobstruction
<=1triangle graph C_3 and spoke graph S(3,2)
<=2110 forbidden minors
Pathwidth2FirbiddenMinors

The set of 110 forbidden minors (Kinnersley and Langston 1992) is illustrated above. They are implemented in the Wolfram Language as GraphData["PathwidthForbidden"].

See also

Graph Bandwidth, Spoke Graph, Treewidth

Explore with Wolfram|Alpha

References

Chlebiková, J. "The Structure of Obstructions to Treewidth and Pathwidth." Disc. Appl. Math. 120, 61-71, 2002.Fellows, M. R. and Langston, M. A. "On Search, Decision and the Efficiency of Polynomial-Time Algorithms." In Proceedings of the 21st ACM Symposium on the Theory of Computing, pp. 501-512, 1989.Kinnersley, N. G. and Langston, M. A. "Obstruction Set Isolation for the Gate Matrix Layout Problem." Disc. Appl. Math. 54, 169-213, 1992.

Cite this as:

Weisstein, Eric W. "Pathwidth." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Pathwidth.html

Subject classifications