Pathwidth
Representation of a graph as a path graph "thickened" by some amount / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Pathwidth?
Summarize this article for a 10 year old
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. 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.[3]
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,[2] and the "vortices" appearing in the general structure theory for minor-closed graph families have bounded pathwidth.[4] 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.[5][6] 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.[7] Additionally, for several special classes of graphs, such as trees, the pathwidth may be computed in polynomial time without dependence on k.[8][9] 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.[10] Path decomposition may also be used to measure the space complexity of dynamic programming algorithms on graphs of bounded treewidth.[11]