Treewidth

 ( Graph Invariants ) 

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. An example of graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly are called k-tree, and the graphs with treewidth at most are called partial k-tree. Many other well-studied graph families also have bounded treewidth.

Treewidth may be formally defined in several equivalent ways: in terms of the size of the largest vertex set in a tree decomposition of the graph, in terms of the size of the largest clique in a chordal completion of the graph, in terms of the maximum order of a haven describing a strategy for a pursuit–evasion game on the graph, or in terms of the maximum order of a bramble, a collection of connected subgraphs that all touch each other.

Treewidth is commonly used as a parameter in the parameterized complexity analysis of graph . Many algorithms that are NP-hard for general graphs, become easier when the treewidth is bounded by a constant.

The concept of treewidth was originally introduced by under the name of dimension. It was later rediscovered by , based on properties that it shares with a different graph parameter, the Hadwiger number. Later it was again rediscovered by and has since been studied by many other authors. pp.354–355

1. Each graph vertex is contained in at least one bag: $\backslash textstyle\backslash bigcup\_i\; X\_i=V$
2. If bags $X\_i$ and $X\_j$ both contain a vertex $v$, then all bags $X\_k$ associated with nodes in the (unique) path of $T$ between $X\_i$ and $X\_j$ also contain $v$ as well. Equivalently, the bags containing vertex $v$ are associated with a connected subtree of $T$.
3. For every edge $(v,w)$ in the graph, there is at least one bag $X\_i$ that contains both $v$ and $w$. That is, vertices are adjacent in the graph only when their corresponding subtrees have a node in common. (However, two vertices may belong to a bag without being adjacent to each other.)

Equivalently, the treewidth of $G$ is one less than the size of the largest clique in the chordal graph containing $G$ with the smallest maximum clique. A chordal graph with this clique size may be obtained by adding to $G$ an edge between every two vertices for which at least one bag contains both vertices.

Treewidth may also be characterized in terms of havens, functions describing an evasion strategy for a certain pursuit–evasion game defined on a graph. A graph $G$ has treewidth $k$ if and only if it has a haven of order $k+1$ but of no higher order, where a haven of order $k+1$ is a function $\backslash beta$ that maps each set $X$ of at most $k$ vertices in $G$ into one of the connected components of $G\backslash setminus\; X$and that obeys the monotonicity property that $\backslash beta(Y)\backslash subseteq\backslash beta(X)$ whenever $X\backslash subset\; Y$.

A similar characterization can also be made using brambles, families of connected subgraphs that all touch each other (meaning either that they share a vertex or are connected by an edge).. The order of a bramble is the smallest hitting set for the family of subgraphs, and the treewidth of a graph is one less than the maximum order of a bramble.

A connected graph with at least two vertices has treewidth 1 if and only if it is a tree. A tree has treewidth one by the same reasoning as for complete graphs (namely, it is chordal, and has maximum clique size two). Conversely, if a graph has a cycle, then every chordal completion of the graph includes at least one triangle consisting of three consecutive vertices of the cycle, from which it follows that its treewidth is at least two.

The do not have bounded treewidth, because the $n\backslash times\; n$ grid graph is a planar graph with treewidth exactly $n$. Therefore, if $F$ is a minor-closed graph family with bounded treewidth, it cannot include all planar graphs. Conversely, if some planar graph cannot occur as a minor for graphs in family $F$, then there is a constant $k$ such that all graphs in $F$ have treewidth at most $k$. That is, the following three conditions are equivalent to each other:.

1. $F$ is a minor-closed family of bounded-treewidth graphs;
2. One of the finitely many forbidden minors characterizing $F$ is planar;
3. $F$ is a minor-closed graph family that does not include all planar graphs.

• For $k=1$, the unique forbidden minor is a 3-vertex cycle graph..
• For $k=2$, the unique forbidden minor is the 4-vertex complete graph $K\_4$.
• For $k=3$, there are four forbidden minors: $K\_5$, the graph of the octahedron, the pentagonal prism prism graph, and the Wagner graph. Of these, the two are planar.; .

Due to the roles the treewidth plays in an enormous number of fields, different practical and theoretical algorithms computing the treewidth of a graph were developed. Depending on the application on hand, one can prefer better approximation ratio, or better dependence in the running time from the size of the input or the treewidth. The table below provides an overview of some of the treewidth algorithms. Here $k$ is the treewidth and $n$ is the number of vertices of an input graph $G$. Each of the algorithms outputs in time $f(k)\backslash cdot\; g(n)$ a decomposition of width given in the Approximation column. For example, the algorithm of in time $2^\{O(k^3)\}\backslash cdot\; n$ either constructs a tree decomposition of the input graph $G$ of width at most $k$ or reports that the treewidth of $G$ is more than $k$. Similarly, the algorithm of in time $2^\{O(k)\}\backslash cdot\; n$ either constructs a tree decomposition of the input graph $G$ of width at most $5k+4$ or reports that the treewidth of $G$ is more than $k$. improved the width of the decomposition to $2k+1$ in the same running time.

It is not known whether determining the treewidth of is NP-complete, or whether their treewidth can be computed in polynomial time.

In practice, an algorithm of can determine the treewidth of graphs with up to 100 vertices and treewidth up to 11, finding a chordal completion of these graphs with the optimal treewidth.

For larger graphs, one can use search-based techniques such as branch and bound search to compute the treewidth. These algorithms are anytime in that when stopped early, they will output an upper bound on the treewidth. An algorithm of this type was proposed in 2004 by Vibhav Gogate and Rina Dechter. To provide a lower bound on treewidth for the branches of this search, they construct a graph minor by repeatedly contracting an edge between a minimum degree vertex and one of its neighbors, until just one vertex remains. The maximum of the minimum degree over these constructed minors is guaranteed to be a lower bound on the treewidth of the graph. Alex Dow and Rich Korf further improved this algorithm using best-first search.

As an example, the problem of graph coloring a graph of treewidth $k$ may be solved by using a dynamic programming algorithm on a tree decomposition of the graph. For each bag $X\_i$ of the tree decomposition, and each partition of the vertices of $X\_i$ into color classes, the algorithm determines whether that coloring is valid and can be extended to all descendant nodes in the tree decomposition, by combining information of a similar type computed and stored at those nodes. The resulting algorithm finds an optimal coloring of an $n$-vertex graph in time $O(k^\{k+O(1)\}n)$, a time bound that makes this problem fixed-parameter tractable.

• Logic operations, such as $\backslash wedge\; ,\backslash vee\; ,\backslash neg\; ,\backslash Rightarrow$
• Membership tests, such as $e\backslash in\; E$, $v\backslash in\; V$
• Quantifications over vertices, edges, sets of vertices, and/or sets of edges, such as $\backslash forall\; v\backslash in\; V$, $\backslash exists\; e\backslash in\; E$, $\backslash exists\; I\backslash subset\; V$, $\backslash forall\; F\backslash subset\; E$
• Vertex–edge incidence tests ($u$ is an endpoint of $e$), and some extensions that allow for things such as optimization.

Consider for example the graph coloring for graphs. For a graph $G=(V,E)$, this problem asks if it is possible to assign each vertex $v\backslash in\; V$ one of three colors such that no two adjacent vertices are assigned the same color. This problem can be expressed in monadic second order logic as where $W\_1$,$W\_2$, $W\_3$ represent the subsets of vertices having each of the three colors, and where the subexpressions $\backslash operatorname\{independent\}(W\_i)$ are defined to mean $$\backslash operatorname\{independent\}(W\_i)\backslash equiv\; \backslash forall\; e\backslash in\; E\backslash \; \backslash exist\; v\backslash in\; V\backslash \; (\backslash operatorname\{endpoint\}(v,e)\backslash wedge\; \backslash neg\; v\backslash in\; W\_i).$$ (It is not necessary to include in this formula the requirement that the sets $W\_i$ be disjoint.) Therefore, by Courcelle's results, the 3-coloring problem can be solved in linear time for a graph given a tree-decomposition of bounded constant treewidth.

defines a class of graph parameters that he calls -functions, which include the treewidth. These functions from graphs to integers are required to be zero on [[graphs with no edges|empty graph]], to be [[minor-monotone|graph minor]] (a function $f$ is referred to as "minor-monotone" if, whenever $H$ is a minor of $G$, one has $f(H)\backslash le\; f(G)$), to increase by one when a new vertex is added that is [[adjacent to all previous vertices|universal vertex]], and to take the larger value from the two subgraphs on either side of a clique [[separator|Vertex separator]]. The set of all such functions forms a [[complete lattice]] under the operations of elementwise minimization and maximization. The top element in this lattice is the treewidth, and the bottom element is the [[Hadwiger number]], the size of the largest [[complete|complete graph]] [[minor|graph minor]] in the given graph.