Treewidth

From testwiki
Revision as of 11:04, 11 November 2024 by imported>Fatupha (Fixed ambiguity: there are graphs of tw 2 that are not sp-graphs (see linked article for source))
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Template:Short description

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 Template:Mvar are called [[k-tree|Template:Math-tree]]s, and the graphs with treewidth at most Template:Mvar are called [[partial k-tree|partial Template:Math-trees]].Template:Sfnp 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 algorithms. 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 Template:Harvs under the name of dimension. It was later rediscovered by Template:Harvs, based on properties that it shares with a different graph parameter, the Hadwiger number. Later it was again rediscovered by Template:Harvs and has since been studied by many other authors.[1]

Definition

A graph with eight vertices, and a tree decomposition of it onto a tree with six nodes. Each graph edge connects two vertices that are listed together at some tree node, and each graph vertex is listed at the nodes of a contiguous subtree of the tree. Each tree node lists at most three vertices, so the width of this decomposition is two.

A tree decomposition of a graph Template:Math is a tree Template:Mvar with nodes Template:Math, where each Template:Mvar is a subset of Template:Mvar, satisfying the following properties[2] (the term node is used to refer to a vertex of Template:Mvar to avoid confusion with vertices of Template:Mvar):

  1. The union of all sets Template:Mvar equals Template:Mvar. That is, each graph vertex is contained in at least one tree node.
  2. If Template:Mvar and Template:Mvar both contain a vertex Template:Mvar, then all nodes Template:Mvar of Template:Mvar in the (unique) path between Template:Mvar and Template:Mvar contain Template:Mvar as well. Equivalently, the tree nodes containing vertex Template:Mvar form a connected subtree of Template:Mvar.
  3. For every edge Template:Math in the graph, there is a subset Template:Mvar that contains both Template:Mvar and Template:Mvar. That is, vertices are adjacent in the graph only when the corresponding subtrees have a node in common.

The width of a tree decomposition is the size of its largest set Template:Mvar minus one. The treewidth Template:Math of a graph Template:Mvar is the minimum width among all possible tree decompositions of Template:Mvar. In this definition, the size of the largest set is diminished by one in order to make the treewidth of a tree equal to one.

Equivalently, the treewidth of Template:Mvar is one less than the size of the largest clique in the chordal graph containing Template:Mvar with the smallest clique number. A chordal graph with this clique size may be obtained by adding to Template:Mvar an edge between every two vertices that both belong to at least one of the sets Template:Mvar.

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 Template:Mvar has treewidth Template:Mvar if and only if it has a haven of order Template:Math but of no higher order, where a haven of order Template:Math is a function Template:Mvar that maps each set Template:Mvar of at most Template:Mvar vertices in Template:Mvar into one of the connected components of Template:Math and that obeys the monotonicity property that Template:Math whenever Template:Math.

A bramble of order four in a 3×3 grid graph, the existence of which shows that the graph has treewidth at least 3

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).[3] 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.

Examples

Every complete graph Template:Mvar has treewidthTemplate:Math. This is most easily seen using the definition of treewidth in terms of chordal graphs: the complete graph is already chordal, and adding more edges cannot reduce the size of its largest clique.

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.

Bounded treewidth

Graph families with bounded treewidth

For any fixed constant Template:Mvar, the graphs of treewidth at most Template:Mvar are called the [[partial k-tree|partial Template:Mvar-trees]]. Other families of graphs with bounded treewidth include the cactus graphs, pseudoforests, series–parallel graphs, outerplanar graphs, Halin graphs, and Apollonian networks.[4] The control-flow graphs arising in the compilation of structured programs also have bounded treewidth, which allows certain tasks such as register allocation to be performed efficiently on them.[5]

The planar graphs do not have bounded treewidth, because the Template:Math grid graph is a planar graph with treewidth exactly Template:Mvar. Therefore, if Template:Mvar 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 Template:Mvar, then there is a constant Template:Mvar such that all graphs in Template:Mvar have treewidth at most Template:Mvar. That is, the following three conditions are equivalent to each other:[6]

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

Forbidden minors

The four forbidden minors for treewidth 3: Template:Math (top-left), the graph of the octahedron (bottom-left), the Wagner graph (top-right), and the graph of the pentagonal prism (bottom-right)

For every finite value of Template:Mvar, the graphs of treewidth at most Template:Mvar may be characterized by a finite set of forbidden minors. (That is, any graph of treewidth Template:Math includes one of the graphs in the set as a minor.) Each of these sets of forbidden minors includes at least one planar graph.

For larger values of Template:Mvar, the number of forbidden minors grows at least as quickly as the exponential of the square root of Template:Mvar.Template:Sfnp However, known upper bounds on the size and number of forbidden minors are much higher than this lower bound.Template:Sfnp

Algorithms

Computing the treewidth

It is NP-complete to determine whether a given graph Template:Mvar has treewidth at most a given variable Template:Mvar.Template:Sfnp However, when Template:Mvar is any fixed constant, the graphs with treewidth Template:Mvar can be recognized, and a width Template:Mvar tree decomposition constructed for them, in linear time.[8] The time dependence of this algorithm on Template:Mvar is exponential.

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 Template:Mvar is the treewidth and Template:Mvar is the number of vertices of an input graph Template:Mvar. Each of the algorithms outputs in time Template:Math a decomposition of width given in the Approximation column. For example, the algorithm of Template:Harvtxt in time Template:Math either constructs a tree decomposition of the input graph Template:Mvar of width at most Template:Mvar or reports that the treewidth of Template:Mvar is more than Template:Mvar. Similarly, the algorithm of Template:Harvtxt in time Template:Math either constructs a tree decomposition of the input graph Template:Mvar of width at most Template:Math or reports that the treewidth of Template:Mvar is more than Template:Mvar. Template:Harvtxt improved this to Template:Math in the same running time.

Approximation Template:Math Template:Math reference
exact Template:Math Template:Math Template:Harvtxt
Template:Math Template:Math Template:Math Template:Harvtxt
Template:Math Template:Math Template:Math Template:Harvtxt
Template:Math (or Template:Math) Template:Math Template:Math Template:Harvtxt
exact Template:Math Template:Math Template:Harvtxt
O(k⋅log⁡k) Template:Math Template:Math Template:Harvtxt
Template:Math Template:Math Template:Math Template:Harvtxt
Template:Math Template:Math Template:Math Template:Harvtxt
exact Template:Math Template:Math Template:Harvtxt
Template:Math Template:Math Template:Math Template:Harvtxt
Template:Math Template:Math Template:Math Template:Harvtxt
Template:Math Template:Math Template:Math Template:Harvtxt
Template:Math Template:Math Template:Math Template:Harvtxt
Template:Math Template:Math Template:Math Template:Harvtxt
Template:Math Template:Math Template:Math Template:Harvtxt
exact Template:Math Template:Math Template:Harvtxt
Template:Math Template:Math Template:Math Template:Harvtxt

Template:Unsolved It is not known whether determining the treewidth of planar graphs is NP-complete, or whether their treewidth can be computed in polynomial time.Template:Sfnp

In practice, an algorithm of Template:Harvtxt 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 (BnB) and best-first search to compute the treewidth. These algorithms are anytime in that when stopped early, they will output an upper bound on the treewidth.

The first BnB algorithm for computing treewidth, called the QuickBB algorithm[9] was proposed by Gogate and Dechter.[10] Since the quality of any BnB algorithm is highly dependent on the quality of the lower bound used, Gogate and Dechter[10] also proposed a novel algorithm for computing a lower-bound on treewidth called minor-min-width.[10] At a high level, the minor-min-width algorithm combines the facts that the treewidth of a graph is never larger than its minimum degree or its minor to yield a lower bound on treewidth. The minor-min-width algorithm repeatedly constructs a graph minor by 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.

Dow and Korf[11] improved the QuickBB algorithm using best-first search. On certain graphs, this best-first search algorithm is an order of magnitude faster than QuickBB.

Solving other problems on graphs of small treewidth

At the beginning of the 1970s, it was observed that a large class of combinatorial optimization problems defined on graphs could be efficiently solved by non serial dynamic programming as long as the graph had a bounded dimension,Template:Sfnp a parameter shown to be equivalent to treewidth by Template:Harvtxt. Later, several authors independently observed at the end of the 1980s[12] that many algorithmic problems that are NP-complete for arbitrary graphs may be solved efficiently by dynamic programming for graphs of bounded treewidth, using the tree-decompositions of these graphs.

As an example, the problem of coloring a graph of treewidth Template:Mvar may be solved by using a dynamic programming algorithm on a tree decomposition of the graph. For each set Template:Mvar of the tree decomposition, and each partition of the vertices of Template:Mvar 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 Template:Mvar-vertex graph in time Template:Math, a time bound that makes this problem fixed-parameter tractable.

Courcelle's theorem

Template:Main For a large class of problems, there is a linear time algorithm to solve a problem from the class if a tree-decomposition with constant bounded treewidth is provided. Specifically, Courcelle's theorem[13] states that if a graph problem can be expressed in the logic of graphs using monadic second order logic, then it can be solved in linear time on graphs with bounded treewidth. Monadic second order logic is a language to describe graph properties that uses the following constructions:

Consider for example the 3-coloring problem for graphs. For a graph Template:Math, this problem asks if it is possible to assign each vertex Template:Math one of the 3 colors such that no two adjacent vertices are assigned the same color. This problem can be expressed in monadic second order logic as follows:

∃W1⊆V:∃W2⊆V:∃W3⊆V:∀v∈V:(v∈W1∨v∈W2∨v∈W3)∧
∀v∈V:∀w∈V:(v,w)∈E⇒(¬(v∈W1∧w∈W1)∧¬(v∈W2∧w∈W2)∧¬(v∈W3∧w∈W3)),

where Template:Math, Template:Math, Template:Math represent the subsets of vertices having each of the 3 colors. 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.

Pathwidth

The pathwidth of a graph has a very similar definition to treewidth via tree decompositions, but is restricted to tree decompositions in which the underlying tree of the decomposition is a path graph. Alternatively, the pathwidth may be defined from interval graphs analogously to the definition of treewidth from chordal graphs. As a consequence, the pathwidth of a graph is always at least as large as its treewidth, but it can only be larger by a logarithmic factor.[4] Another parameter, the graph bandwidth, has an analogous definition from proper interval graphs, and is at least as large as the pathwidth. Other related parameters include the tree-depth, a number that is bounded for a minor-closed graph family if and only if the family excludes a path, and the degeneracy, a measure of the sparsity of a graph that is at most equal to its treewidth.

Grid minor size

Because the treewidth of an Template:Math grid graph is Template:Mvar, the treewidth of a graph Template:Mvar is always greater than or equal to the size of the largest square grid minor of Template:Mvar. In the other direction, the grid minor theorem by Robertson and Seymour shows that there exists an unbounded function Template:Mvar such that the largest square grid minor has size at least Template:Math where Template:Mvar is the treewidth.[14] The best bounds known on Template:Mvar are that Template:Mvar must be at least Template:Math for some fixed constant Template:Math, and at most[15]

O(r/log⁡r).

For the Template:Math notation in the lower bound, see big O notation. Tighter bounds are known for restricted graph families, leading to efficient algorithms for many graph optimization problems on those families through the theory of bidimensionality.Template:Sfnp Halin's grid theorem provides an analogue of the relation between treewidth and grid minor size for infinite graphs.Template:Sfnp

Diameter and local treewidth

A family Template:Mvar of graphs closed under taking subgraphs is said to have bounded local treewidth, or the diameter-treewidth property, if the treewidth of the graphs in the family is upper bounded by a function of their diameter. If the class is also assumed to be closed under taking minors, then Template:Mvar has bounded local treewidth if and only if one of the forbidden minors for Template:Mvar is an apex graph.Template:Sfnp The original proofs of this result showed that treewidth in an apex-minor-free graph family grows at most doubly exponentially as a function of diameter;[16] later this was reduced to singly exponentialTemplate:Sfnp and finally to a linear bound.Template:Sfnp Bounded local treewidth is closely related to the algorithmic theory of bidimensionality,[17] and every graph property definable in first order logic can be decided for an apex-minor-free graph family in an amount of time that is only slightly superlinear.Template:Sfnp

It is also possible for a class of graphs that is not closed under minors to have bounded local treewidth. In particular this is trivially true for a class of bounded degree graphs, as bounded diameter subgraphs have bounded size. Another example is given by 1-planar graphs, graphs that can be drawn in the plane with one crossing per edge, and more generally for the graphs that can be drawn on a surface of bounded genus with a bounded number of crossings per edge. As with minor-closed graph families of bounded local treewidth, this property has pointed the way to efficient approximation algorithms for these graphs.Template:Sfnp

Hadwiger number and S-functions

Template:Harvtxt defines a class of graph parameters that he calls Template:Mvar-functions, which include the treewidth. These functions from graphs to integers are required to be zero on graphs with no edges, to be minor-monotone (a function Template:Mvar is referred to as "minor-monotone" if, whenever Template:Mvar is a minor of Template:Mvar, one has Template:Math), to increase by one when a new vertex is added that is adjacent to all previous vertices, and to take the larger value from the two subgraphs on either side of a clique 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 minor in the given graph.

Notes

Template:Reflist

References

Template:Refbegin

Template:Refend

  1. ↑ Template:Harvtxt pp.354–355
  2. ↑ Template:Harvtxt section 12.3
  3. ↑ Template:Harvtxt.
  4. ↑ 4.0 4.1 4.2 4.3 Template:Harvtxt.
  5. ↑ Template:Harvtxt.
  6. ↑ Template:Harvtxt.
  7. ↑ Template:Harvtxt; Template:Harvtxt.
  8. ↑ Template:Harvtxt.
  9. ↑ Template:Cite web
  10. ↑ 10.0 10.1 10.2 Template:Cite arXiv
  11. ↑ Template:Cite web
  12. ↑ Template:Harvtxt; Template:Harvtxt; Template:Harvtxt.
  13. ↑ Template:Harvtxt; Template:Harvtxt
  14. ↑ Robertson, Seymour. Graph minors. V. Excluding a planar graph. [1] Template:Open access
  15. ↑ Template:Harvtxt
  16. ↑ Template:Harvtxt; Template:Harvtxt.
  17. ↑ Template:Harvtxt; Template:Harvtxt.
Retrieved from "https://en.wiki.beta.math.wmflabs.org/w/index.php?title=Treewidth&oldid=14940"