“Tree decomposition”的意思、由来-开放百科全书

词条

Tree decomposition

释义

Definition
Treewidth
Dynamic programming
See also
Notes
References

{{about|tree structure of graphs|decomposition of graphs into trees|Graph theory#Decomposition problems}}

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.

In machine learning, tree decompositions are also called junction trees, clique trees, or join trees; they play an important role in problems like probabilistic inference, constraint satisfaction, query optimization,{{citation needed|reason=It is not apparent from the linked Wikipedia article how tree decompositions are used there. Further neither this nor the linked Wikipedia article references any scientific paper on the subject. It is impossible for someone not knowledgeable in that domain to verify this. |date=June 2016}} and matrix decomposition.

The concept of tree decompositions was originally introduced by {{harvs|last=Halin|first=Rudolf|authorlink=Rudolf Halin|year=1976|txt}}. Later it was rediscovered by {{harvs|first1=Neil|last1=Robertson|author1-link=Neil Robertson (mathematician)|first2=Paul|last2=Seymour|author2-link=Paul Seymour (mathematician)|year=1984|txt}} and has since been studied by many other authors.^[1]

Definition

Intuitively, a tree decomposition represents the vertices of a given graph G as subtrees of a tree, in such a way that vertices in the given graph are adjacent only when the corresponding subtrees intersect. Thus, G forms a subgraph of the intersection graph of the subtrees. The full intersection graph is a chordal graph.

Each subtree associates a graph vertex with a set of tree nodes. To define this formally, we represent each tree node as the set of vertices associated with it.

Thus, given a graph G = (V, E), a tree decomposition is a pair (X, T), where X = {X₁, ..., X_n} is a family of subsets of V, and T is a tree whose nodes are the subsets X_i, satisfying the following properties:^[2]

The union of all sets X_i equals V. That is, each graph vertex is associated with at least one tree node.
For every edge (v, w) in the graph, there is a subset X_i that contains both v and w. That is, vertices are adjacent in the graph only when the corresponding subtrees have a node in common.
If X_i and X_j both contain a vertex v, then all nodes X_k of the tree in the (unique) path between X_i and X_j contain v as well. That is, the nodes associated with vertex v form a connected subset of T. This is also known as coherence, or the running intersection property. It can be stated equivalently that if , and are nodes, and is on the path from to , then .

The tree decomposition of a graph is far from unique; for example, a trivial tree decomposition contains all vertices of the graph in its single root node.

A tree decomposition in which the underlying tree is a path graph is called a path decomposition, and the width parameter derived from these special types of tree decompositions is known as pathwidth.

A tree decomposition (X, T = (I, F)) of treewidth k is smooth, if for all , and for all .^[3]

The minimum number of trees in a tree decomposition is the tree number of G.

Treewidth

The width of a tree decomposition is the size of its largest set X_i minus one. The treewidth tw(G) of a graph G is the minimum width among all possible tree decompositions of G. 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. Treewidth may also be defined from other structures than tree decompositions, including chordal graphs, brambles, and havens.

It is NP-complete to determine whether a given graph G has treewidth at most a given variable k.^[4]

However, when k is any fixed constant, the graphs with treewidth k can be recognized, and a width k tree decomposition constructed for them, in linear time.^[5] The time dependence of this algorithm on k is exponential.

Dynamic programming

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,{{sfnp|Bertelé|Brioschi|1972}} a parameter related to treewidth. Later, several authors independently observed, at the end of the 1980s,^[6] 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, consider the problem of finding the maximum independent set in a graph of treewidth k. To solve this problem, first choose one of the nodes of the tree decomposition to be the root, arbitrarily. For a node X_i of the tree decomposition, let D_i be the union of the sets X_j descending from X_i. For an independent set S ⊂ X_i, let A(S,i) denote the size of the largest independent subset I of D_i such that I ∩ X_i = S. Similarly, for an adjacent pair of nodes X_i and X_j, with X_i farther from the root of the tree than X_j, and an independent set S ⊂ X_i ∩ X_j, let B(S,i,j) denote the size of the largest independent subset I of D_i such that I ∩ X_i ∩ X_j = S. We may calculate these A and B values by a bottom-up traversal of the tree:

where the sum in the calculation of is over the children of node .

At each node or edge, there are at most 2^k sets S for which we need to calculate these values, so if k is a constant then the whole calculation takes constant time per edge or node. The size of the maximum independent set is the largest value stored at the root node, and the maximum independent set itself can be found (as is standard in dynamic programming algorithms) by backtracking through these stored values starting from this largest value. Thus, in graphs of bounded treewidth, the maximum independent set problem may be solved in linear time. Similar algorithms apply to many other graph problems.

This dynamic programming approach is used in machine learning via the junction tree algorithm for belief propagation in graphs of bounded treewidth. It also plays a key role in algorithms for computing the treewidth and constructing tree decompositions: typically, such algorithms have a first step that approximates the treewidth, constructing a tree decomposition with this approximate width, and then a second step that performs dynamic programming in the approximate tree decomposition to compute the exact value of the treewidth.^[3]

Notes

1. ^{{harvtxt|Diestel|2005}} pp.354–355
2. ^{{harvtxt|Diestel|2005}} section 12.3
3. ^¹{{harvtxt|Bodlaender|1996}}.
4. ^{{harvtxt|Arnborg|Corneil|Proskurowski|1987}}.
5. ^{{harvtxt|Bodlaender|1996}}.
6. ^{{harvtxt|Arnborg|Proskurowski|1989}}; {{harvtxt|Bern|Lawler|Wong|1987}}; {{harvtxt|Bodlaender|1988}}.

References

{{citation

| last1 = Arnborg | first1 = S.
| last2 = Corneil | first2 = D. | author2-link = Derek Corneil
| last3 = Proskurowski | first3 = A.
| title = Complexity of finding embeddings in a k-tree
| journal = SIAM Journal on Matrix Analysis and Applications
| volume = 8 | issue = 2 | year = 1987 | pages = 277–284 | doi = 10.1137/0608024}}.

{{citation

| last1 = Arnborg | first1 = S.
| last2 = Proskurowski | first2 = A.
| title = Linear time algorithms for NP-hard problems restricted to partial k-trees
| journal = Discrete Applied Mathematics
| volume = 23 | issue = 1 | year = 1989 | pages = 11–24 | doi = 10.1016/0166-218X(89)90031-0}}.

{{citation

| last1 = Bern | first1 = M. W.
| last2 = Lawler | first2 = E. L. | author2-link = Eugene Lawler
| last3 = Wong | first3 = A. L.
| title = Linear-time computation of optimal subgraphs of decomposable graphs
| journal = Journal of Algorithms
| volume = 8 | issue = 2 | year = 1987 | pages = 216–235 | doi = 10.1016/0196-6774(87)90039-3}}.

{{citation

| last1 = Bertelé | first1 = Umberto
| last2 = Brioschi | first2 = Francesco
| title = Nonserial Dynamic Programming
| year = 1972
| publisher = Academic Press
| isbn = 0-12-093450-7}}.

{{citation

| last = Bodlaender | first = Hans L. | authorlink = Hans L. Bodlaender
| contribution = Dynamic programming on graphs with bounded treewidth
| title = Proc. 15th International Colloquium on Automata, Languages and Programming
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
| volume = 317 | year = 1988 | pages = 105–118
| doi = 10.1007/3-540-19488-6_110}}.

{{citation

| last = Bodlaender | first = Hans L. | authorlink = Hans L. Bodlaender
| title = A linear time algorithm for finding tree-decompositions of small treewidth
| journal = SIAM Journal on Computing
| volume = 25 | issue = 6 | year = 1996 | pages = 1305–1317 | doi = 10.1137/S0097539793251219}}.

{{Citation

}}.

{{Citation

}}.

{{citation

| last1 = Robertson | first1 = Neil | authorlink1 = Neil Robertson (mathematician)
| last2 = Seymour | first2 = Paul D. | authorlink2 = Paul Seymour (mathematician)
| title = Graph minors III: Planar tree-width
| journal = Journal of Combinatorial Theory, Series B
| volume = 36
| issue = 1 | year = 1984 | pages = 49–64
| doi = 10.1016/0095-8956(84)90013-3}}.{{refend}}

3 : Trees (graph theory)|Graph minor theory|Graph theory objects

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

Definition

Treewidth

Dynamic programming

See also

Notes

References