HOME

TheInfoList



OR:

In
graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, a path decomposition of a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
is, informally, a representation of as a "thickened"
path graph In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...
, and the pathwidth of is a number that measures how much the path was thickened to form . More formally, a path-decomposition is a sequence of subsets of vertices of 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 In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is comple ...
size in an interval supergraph of ), vertex separation number, or node searching number. Pathwidth and path-decompositions are closely analogous to
treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...
and
tree decomposition In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. Tree decompositions are also called junction trees ...
s. They play a key role in the theory of
graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...
s: the families of graphs that are closed under
graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...
s and do not include all
forest A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...
s 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 Very large-scale integration (VLSI) is the process of creating an integrated circuit (IC) by combining millions or billions of MOS transistors onto a single chip. VLSI began in the 1970s when MOS integrated circuit (Metal Oxide Semiconductor) c ...
design,
graph drawing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graph (discrete mathematics), graphs arising from applications such a ...
, 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 In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...
: testing whether a graph has pathwidth can be solved in an amount of time that depends linearly on the size of the graph but superexponentially on . Additionally, for several special classes of graphs, such as
trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...
, the pathwidth may be computed in polynomial time without dependence on . Many problems in graph algorithms may be solved efficiently on graphs of bounded pathwidth, by using
dynamic programming Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...
on a path-decomposition of the graph.. Path decomposition may also be used to measure the
space complexity The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it ex ...
of dynamic programming algorithms on graphs of bounded
treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...
..


Definition

In the first of their famous series of papers on
graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...
s, define a path-decomposition of a graph to be a sequence of subsets of vertices of , with two properties: #For each edge of , there exists an such that both endpoints of the edge belong to subset , and #For every three indices , X_i \cap X_k \subseteq X_j. 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 In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. Tree decompositions are also called junction trees ...
in which the underlying tree of the decomposition is a
path graph In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...
. The width of a path-decomposition is defined in the same way as for tree-decompositions, as , and the pathwidth of is the minimum width of any path-decomposition of . The subtraction of one from the size of in this definition makes little difference in most applications of pathwidth, but is used to make the pathwidth of a
path graph In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...
be equal to one.


Alternative characterizations

As describes, pathwidth can be characterized in many equivalent ways.


Gluing sequences

A path decomposition can be described as a sequence of graphs 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 . The graphs may be taken as the
induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...
s of the sets 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 , and in the other direction one may recover the sets as the vertex sets of the graphs . The width of the path decomposition is then one less than the maximum number of vertices in one of the graphs .


Interval thickness

The pathwidth of any graph is equal to one less than the smallest clique number of an
interval graph In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. In ...
that contains as a subgraph. That is, for every path decomposition of one can find an interval supergraph of , and for every interval supergraph of one can find a path decomposition of , such that the width of the decomposition is one less than the clique number of the interval graph. In one direction, suppose a path decomposition of is given. Then one may represent the nodes of the decomposition as points on a line (in path order) and represent each vertex as a closed interval having these points as endpoints. In this way, the path decomposition nodes containing correspond to the representative points in the interval for . The
intersection graph In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...
of the intervals formed from the vertices of is an interval graph that contains as a subgraph. Its maximal cliques are given by the sets of intervals containing the representative points, and its maximum clique size is one plus the pathwidth of . In the other direction, if is a subgraph of an interval graph with clique number , then has a path decomposition of width whose nodes are given by the
maximal clique In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is compl ...
s of the interval graph. 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 , , , , and ; the maximum clique size is three and the width of this path decomposition is two. This equivalence between pathwidth and interval thickness is closely analogous to the equivalence between treewidth and the minimum clique number (minus one) of a
chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...
of which the given graph is a subgraph. Interval graphs are a special case of chordal graphs, and chordal graphs can be represented as intersection graphs of subtrees of a common tree generalizing the way that interval graphs are intersection graphs of subpaths of a path.


Vertex separation number

Suppose that the vertices of a graph are
linearly ordered In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...
. Then the vertex separation number of is the smallest number such that, for each vertex , at most vertices are earlier than in the ordering but that have or a later vertex as a neighbor. The vertex separation number of is the minimum vertex separation number of any linear ordering of . The vertex separation number was defined by , and is equal to the pathwidth of . This follows from the earlier equivalence with interval graph clique numbers: if is a subgraph of an interval graph , represented (as in the figure) in such a way that all interval endpoints are distinct, then the ordering of the left endpoints of the intervals of has vertex separation number one less than the clique number of . And in the other direction, from a linear ordering of one may derive an interval representation in which the left endpoint of the interval for a vertex is its position in the ordering and the right endpoint is the position of the neighbor of that comes last in the ordering.


Node searching number

The node searching game on a graph is a form of
pursuit–evasion Pursuit–evasion (variants of which are referred to as cops and robbers and graph searching) is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment. Early ...
in which a set of searchers collaborate to track down a fugitive hiding in a graph. The searchers are placed on vertices of the graph while the fugitive may be in any edge of the graph, and the fugitive's location and moves are hidden from the searchers. In each turn, some or all of the searchers may move (arbitrarily, not necessarily along edges) from one vertex to another, and then the fugitive may move along any path in the graph that does not pass through a searcher-occupied vertex. The fugitive is caught when both endpoints of his edge are occupied by searchers. The node searching number of a graph is the minimum number of searchers needed to ensure that the fugitive can be guaranteed to be caught, no matter how he moves. As show, the node searching number of a graph equals its interval thickness. The optimal strategy for the searchers is to move the searchers so that in successive turns they form the separating sets of a linear ordering with minimal vertex separation number.


Bounds

Every -vertex graph with pathwidth has at most edges, and the maximal pathwidth- graphs (graphs to which no more edges can be added without increasing the pathwidth) have exactly this many edges. A maximal pathwidth- graph must be either a -path or a -caterpillar, two special kinds of -tree. A -tree is a
chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...
with exactly
maximal clique In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is compl ...
s, each containing vertices; in a -tree that is not itself a -clique, each maximal clique either separates the graph into two or more components, or it contains a single leaf vertex, a vertex that belongs to only a single maximal clique. A -path is a -tree with at most two leaves, and a -caterpillar is a -tree that can be partitioned into a -path and a set of -leaves each adjacent to a separator -clique of the -path. In particular the maximal graphs of pathwidth one are exactly the
caterpillar tree In graph theory, a caterpillar or caterpillar tree is a tree in which all the vertices are within distance 1 of a central path. Caterpillars were first studied in a series of papers by Harary and Schwenk. The name was suggested by Arthur Hob ...
s. Since path-decompositions are a special case of tree-decompositions, the pathwidth of any graph is greater than or equal to its
treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...
. The pathwidth is also less than or equal to the cutwidth, the minimum number of edges that cross any cut between lower-numbered and higher-numbered vertices in an optimal linear arrangement of the vertices of a graph; this follows because the vertex separation number, the number of lower-numbered vertices with higher-numbered neighbors, can at most equal the number of cut edges. For similar reasons, the cutwidth is at most the pathwidth times the maximum degree of the vertices in a given graph. Any -vertex
forest A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...
has pathwidth . For, in a forest, one can always find a constant number of vertices the removal of which leaves a forest that can be partitioned into two smaller subforests with at most vertices each. A linear arrangement formed by recursively partitioning each of these two subforests, placing the separating vertices between them, has logarithmic vertex searching number. The same technique, applied to a tree-decomposition of a graph, shows that, if the treewidth of an -vertex graph is , then the pathwidth of is . Since
outerplanar graph In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing. Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two fo ...
s,
series–parallel graph In graph theory, series–parallel graphs are graphs with two distinguished vertices called ''terminals'', formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits. Definition and t ...
s, and
Halin graph In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none o ...
s all have bounded treewidth, they all also have at most logarithmic pathwidth. As well as its relations to treewidth, pathwidth is also related to
clique-width In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs. It is defined as the minimum num ...
and cutwidth, via
line graph In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...
s; the line graph of a graph has a vertex for each edge of and two vertices in are adjacent when the corresponding two edges of share an endpoint. Any family of graphs has bounded pathwidth if and only if its line graphs have bounded linear clique-width, where linear clique-width replaces the disjoint union operation from clique-width with the operation of adjoining a single new vertex. If a connected graph with three or more vertices has maximum degree three, then its cutwidth equals the vertex separation number of its line graph. In any planar graph, the pathwidth is at most proportional to the square root of the number of vertices. 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 In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of verti ...
to find a set of vertices the removal of which separates the graph into two subgraphs of at most 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. Since, like planar graphs, the graphs in any fixed minor-closed graph family have separators of size , it follows that the pathwidth of the graphs in any fixed minor-closed family is again . For some classes of planar graphs, the pathwidth of the graph and the pathwidth of its
dual graph In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-lo ...
must be within a constant factor of each other: bounds of this form are known for biconnected outerplanar graphs and for polyhedral graphs. For 2-connected planar graphs, the pathwidth of the dual graph is less than the pathwidth of the line graph. It remains open whether the pathwidth of a planar graph and its dual are always within a constant factor of each other in the remaining cases. In some classes of graphs, it has been proven that the pathwidth and treewidth are always equal to each other: this is true for
cograph In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...
s,.
permutation graph In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be ...
s,. the complements of
comparability graph In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable grap ...
s,. and the comparability graphs of
interval order In mathematics, especially order theory, the interval order for a collection of intervals on the real line is the partial order corresponding to their left-to-right precedence relation—one interval, ''I''1, being considered less than another, '' ...
s.. In any
cubic graph In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bi ...
, or more generally any graph with maximum vertex degree three, the pathwidth is at most , where is the number of vertices in the graph. There exist cubic graphs with pathwidth , but it is not known how to reduce this gap between this
lower bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an eleme ...
and the upper bound..


Computing path-decompositions

It is
NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
to determine whether the pathwidth of a given graph is at most , when is a variable given as part of the input.; ; ; . The best known worst-case time bounds for computing the pathwidth of arbitrary -vertex graphs are of the form for some constant . 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.


Fixed-parameter tractability

Pathwidth is
fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...
: for any constant , it is possible to test whether the pathwidth is at most , and if so to find a path-decomposition of width , in linear time. In general, these algorithms operate in two phases. In the first phase, the assumption that the graph has pathwidth is used to find a path-decomposition or tree-decomposition that is not optimal, but whose width can be bounded as a function of . In the second phase, a
dynamic programming Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...
algorithm is applied to this decomposition in order to find the optimal decomposition. However, the time bounds for known algorithms of this type are exponential in , impractical except for the smallest values of . For the case an explicit linear-time algorithm based on a structural decomposition of pathwidth-2 graphs is given by .


Special classes of graphs

surveys the complexity of computing the pathwidth on various special classes of graphs. Determining whether the pathwidth of a graph is at most remains NP-complete when is restricted to bounded-degree graphs,. planar graphs, planar graphs of bounded degree,
chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...
s, chordal dominoes, the complements of
comparability graph In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable grap ...
s, and bipartite
distance-hereditary graph In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any ...
s.. It follows immediately that it is also NP-complete for the graph families that contain the bipartite distance-hereditary graphs, including the bipartite graphs, chordal bipartite graphs, distance-hereditary graphs, and circle graphs. However, the pathwidth may be computed in linear time for trees and forests,.; ; ; ; ; ; . It may also be computed in polynomial time for graphs of bounded treewidth including
series–parallel graph In graph theory, series–parallel graphs are graphs with two distinguished vertices called ''terminals'', formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits. Definition and t ...
s,
outerplanar graph In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing. Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two fo ...
s, and
Halin graph In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none o ...
s,; as well as for
split graph In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by , and independently introduced by . A split graph may have m ...
s, for the complements of chordal graphs, for
permutation graph In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be ...
s, for
cograph In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...
s, for
circular-arc graph In graph theory, a circular-arc graph is the intersection graph of a set of arcs on the circle. It has one vertex for each arc in the set, and an edge between every pair of vertices corresponding to arcs that intersect. Formally, let :I_1, I_2, ...
s, for the comparability graphs of interval orders, and of course for
interval graph In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. In ...
s themselves, since in that case the pathwidth is just one less than the maximum number of intervals covering any point in an interval representation of the graph.


Approximation algorithms

It is NP-hard to approximate the pathwidth of a graph to within an additive constant. The best known
approximation ratio An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ' ...
of a polynomial time approximation algorithm for pathwidth is . For earlier approximation algorithms for pathwidth, see and . For approximations on restricted classes of graphs, see .


Graph minors

A minor of a graph is another graph formed from by contracting edges, removing edges, and removing vertices. Graph minors have a deep theory in which several important results involve pathwidth.


Excluding a forest

If a family of graphs is closed under taking minors (every minor of a member of is also in ), then by the
Robertson–Seymour theorem In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is cl ...
can be characterized as the graphs that do not have any minor in , where is a finite set of forbidden minors.. For instance,
Wagner's theorem In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither ''K''5 (the complete graph on fi ...
states that the planar graphs are the graphs that have neither the
complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
nor the
complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory i ...
as minors. In many cases, the properties of and the properties of are closely related, and the first such result of this type was by , and relates bounded pathwidth with the existence of a
forest A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...
in the family of forbidden minors. Specifically, define a family of graphs to have ''bounded pathwidth'' if there exists a constant such that every graph in has pathwidth at most . Then, a minor-closed family has bounded pathwidth if and only if the set of forbidden minors for includes at least one forest. In one direction, this result is straightforward to prove: if does not include at least one forest, then the -minor-free graphs do not have bounded pathwidth. For, in this case, the -minor-free graphs include all forests, and in particular they include the
perfect binary tree In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
s. But a perfect binary tree with levels has pathwidth , so in this case the -minor-free-graphs have unbounded pathwidth. In the other direction, if contains an -vertex forest, then the -minor-free graphs have pathwidth at most .


Obstructions to bounded pathwidth

The property of having pathwidth at most is, itself, closed under taking minors: if has a path-decomposition with width at most , then the same path-decomposition remains valid if any edge is removed from , and any vertex can be removed from and from its path-decomposition without increasing the width. Contraction of an edge, also, can be accomplished without increasing the width of the decomposition, by merging the sub-paths representing the two endpoints of the contracted edge. Therefore, the graphs of pathwidth at most can be characterized by a set of excluded minors.; ; , p. 8. Although necessarily includes at least one forest, it is not true that all graphs in are forests: for instance, consists of two graphs, a seven-vertex tree and the triangle . However, the set of trees in may be precisely characterized: these trees are exactly the trees that can be formed from three trees in by connecting a new root vertex by an edge to an arbitrarily chosen vertex in each of the three smaller trees. For instance, the seven-vertex tree in is formed in this way from the two-vertex tree (a single edge) in . Based on this construction, the number of forbidden minors in can be shown to be at least . The complete set of forbidden minors for pathwidth-2 graphs has been computed; it contains 110 different graphs.


Structure theory

The
graph structure theorem In mathematics, the graph structure theorem is a major result in the area of graph theory. The result establishes a deep and fundamental connection between the theory of graph minors and topological embeddings. The theorem is stated in the seven ...
for minor-closed graph families states that, for any such family , the graphs in can be decomposed into
clique-sum In graph theory, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs ''G'' and ''H'' each contain cliques of equal size, th ...
s of graphs that can be embedded onto surfaces of bounded
genus Genus ( plural genera ) is a taxonomic rank used in the biological classification of extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In the hierarchy of biological classification, genus com ...
, together with a bounded number of apexes and vortices for each component of the clique-sum. An apex is a vertex that may be adjacent to any other vertex in its component, while a vortex is a graph of bounded pathwidth that is glued into one of the faces of the bounded-genus embedding of a component. The cyclic ordering of the vertices around the face into which a vortex is embedded must be compatible with the path decomposition of the vortex, in the sense that breaking the cycle to form a linear ordering must lead to an ordering with bounded vertex separation number. This theory, in which pathwidth is intimately connected to arbitrary minor-closed graph families, has important algorithmic applications.


Applications


VLSI

In
VLSI Very large-scale integration (VLSI) is the process of creating an integrated circuit (IC) by combining millions or billions of MOS transistors onto a single chip. VLSI began in the 1970s when MOS integrated circuit (Metal Oxide Semiconductor) c ...
design, the vertex separation problem was originally studied as a way to partition circuits into smaller subsystems, with a small number of components on the boundary between the subsystems. use interval thickness to model the number of tracks needed in a one-dimensional layout of a VLSI circuit, formed by a set of modules that need to be interconnected by a system of nets. In their model, one forms a graph in which the vertices represent nets, and in which two vertices are connected by an edge if their nets both connect to the same module; that is, if the modules and nets are interpreted as forming the nodes and hyperedges of a
hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph H is a pair H = (X,E) wh ...
then the graph formed from them is its
line graph In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...
. An interval representation of a supergraph of this line graph, together with a coloring of the supergraph, describes an arrangement of the nets along a system of horizontal tracks (one track per color) in such a way that the modules can be placed along the tracks in a linear order and connect to the appropriate nets. The fact that interval graphs are
perfect graph In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is perfe ...
s implies that the number of colors needed, in an optimal arrangement of this type, is the same as the clique number of the interval completion of the net graph. Gate matrix layout is a specific style of CMOS VLSI layout for Boolean logic circuits. In gate matrix layouts, signals are propagated along "lines" (vertical line segments) while each gate of the circuit is formed by a sequence of device features that lie along a horizontal line segment. Thus, the horizontal line segment for each gate must cross the vertical segments for each of the lines that form inputs or outputs of the gate. As in the layouts of , a layout of this type that minimizes the number of vertical tracks on which the lines are to be arranged can be found by computing the pathwidth of a graph that has the lines as its vertices and pairs of lines sharing a gate as its edges.. The same algorithmic approach can also be used to model folding problems in programmable logic arrays.


Graph drawing

Pathwidth has several applications to
graph drawing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graph (discrete mathematics), graphs arising from applications such a ...
: *The minimal graphs that have a given crossing number have pathwidth that is bounded by a function of their crossing number.. *The number of parallel lines on which the vertices of a tree can be drawn with no edge crossings (under various natural restrictions on the ways that adjacent vertices can be placed with respect to the sequence of lines) is proportional to the pathwidth of the tree. *A ''k''-crossing ''h''-layer drawing of a graph ''G'' is a placement of the vertices of ''G'' onto ''h'' distinct horizontal lines, with edges routed as monotonic polygonal paths between these lines, in such a way that there are at most ''k'' crossings. The graphs with such drawings have pathwidth that is bounded by a function of ''h'' and ''k''. Therefore, when ''h'' and ''k'' are both constant, it is possible in linear time to determine whether a graph has a ''k''-crossing ''h''-layer drawing.. *A graph with ''n'' vertices and pathwidth ''p'' can be embedded into a three-dimensional grid of size in such a way that no two edges (represented as straight line segments between grid points) intersect each other. Thus, graphs of bounded pathwidth have embeddings of this type with linear volume.


Compiler design

In the
compilation Compilation may refer to: *In computer programming, the translation of source code into object code by a compiler **Compilation error **Compilation unit *Product bundling, a marketing strategy used to sell multiple products *Compilation thesis M ...
of
high-level programming language In computer science, a high-level programming language is a programming language with strong abstraction from the details of the computer. In contrast to low-level programming languages, it may use natural language ''elements'', be easier to us ...
s, pathwidth arises in the problem of reordering sequences of straight-line code (that is, code with no
control flow In computer science, control flow (or flow of control) is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated. The emphasis on explicit control flow distinguishes an ''im ...
branches or loops) in such a way that all the values computed in the code can be placed in machine registers instead of having to be spilled into main memory. In this application, one represents the code to be compiled as a
directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
in which the nodes represent the input values to the code and the values computed by the operations within the code. An edge from node ''x'' to node ''y'' in this DAG represents the fact that value ''x'' is one of the inputs to operation ''y''. A
topological ordering In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge ''uv'' from vertex ''u'' to vertex ''v'', ''u'' comes before ''v'' in the ordering. For in ...
of the vertices of this DAG represents a valid reordering of the code, and the number of registers needed to evaluate the code in a given ordering is given by the vertex separation number of the ordering.. For any fixed number ''w'' of machine registers, it is possible to determine in linear time whether a piece of straight-line code can be reordered in such a way that it can be evaluated with at most ''w'' registers. 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. Once a path decomposition has been found, a topological ordering of width ''w'' (if one exists) can be found using dynamic programming, again in linear time.


Linguistics

describe an application of path-width in
natural language processing Natural language processing (NLP) is an interdisciplinary subfield of linguistics, computer science, and artificial intelligence concerned with the interactions between computers and human language, in particular how to program computers to pro ...
. In this application, sentences are modeled as graphs, in which the vertices represent words and the edges represent relationships between words; for instance if an adjective modifies a noun in the sentence then the graph would have an edge between those two words. Due to the limited capacity of human short-term memory, 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.


Exponential algorithms

Many problems in graph algorithms may be solved efficiently on graphs of low pathwidth, by using
dynamic programming Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...
on a path-decomposition of the graph. 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 On graphs of bounded pathwidth, this approach leads to fixed-parameter tractable algorithms, parametrized by the pathwidth. Such results are not frequently found in the literature because they are subsumed by similar algorithms parametrized by the treewidth; however, pathwidth arises even in treewidth-based dynamic programming algorithms in measuring the
space complexity The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it ex ...
of these algorithms. The same dynamic programming method also can be applied to graphs with unbounded pathwidth, leading to algorithms that solve unparametrized graph problems in
exponential time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
. 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(2''n''/6 + o(''n'')), faster than previous known methods. A similar approach leads to improved exponential-time algorithms for the
maximum cut For a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets and , such that the number of edges between and is as large as possible. Fin ...
and
minimum dominating set In graph theory, a dominating set for a graph is a subset of its vertices, such that any vertex of is either in , or has a neighbor in . The domination number is the number of vertices in a smallest dominating set for . The dominating set ...
problems in cubic graphs, and for several other NP-hard optimization problems.; .


See also

*
Boxicity In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969. The boxicity of a graph is the minimum dimension in which a given graph can be represented as an intersection graph of axis-parallel box (shape), boxes. That i ...
, a different way of measuring the complexity of an arbitrary graph in terms of interval graphs * Cutwidth, the minimum possible width of a linear ordering of the vertices of a graph *
Tree-depth In graph theory, the tree-depth of a connected undirected graph G is a numerical invariant of G, the minimum height of a Trémaux tree for a supergraph of G. This invariant and its close relatives have gone under many different names in the lite ...
, a number that is bounded for a minor-closed graph family if and only if the family excludes a path *
Degeneracy Degeneracy, degenerate, or degeneration may refer to: Arts and entertainment * ''Degenerate'' (album), a 2010 album by the British band Trigger the Bloodshed * Degenerate art, a term adopted in the 1920s by the Nazi Party in Germany to descri ...
, a measure of the sparsity of a graph that is at most equal to its path width *
Graph bandwidth In graph theory, the graph bandwidth problem is to label the vertices of a graph with distinct integers so that the quantity \max\ is minimized ( is the edge set of ). The problem may be visualized as placing the vertices of a graph at distin ...
, a different NP-complete optimization problem involving linear layouts of graphs *
Strahler number In mathematics, the Strahler number or Horton–Strahler number of a mathematical tree is a numerical measure of its branching complexity. These numbers were first developed in hydrology by and ; in this application, they are referred to as the ...
, a measure of the complexity of rooted trees defined similarly to pathwidth of unrooted trees


Notes


References

*. *. *. *. *. *. *. *. *. * *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. As cited by . *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. {{refend Graph minor theory Graph invariants