Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Tree decomposition
Summary
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, clique trees, or join trees. They play an important role in problems like probabilistic inference, constraint satisfaction, query optimization, and matrix decomposition.
The concept of tree decomposition was originally introduced by . Later it was rediscovered by and has since been studied by many other authors.
Intuitively, a tree decomposition represents the vertices of a given graph G as subtrees of a tree, in such a way that vertices in G 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_1, ..., X_n} is a family of subsets (sometimes called bags) of V, and T is a tree whose nodes are the subsets X_i, satisfying the following properties:
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 X_i, X_j and X_k are nodes, and X_k is on the path from X_i to X_j, 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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related concepts (7)
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, clique trees, or join trees. They play an important role in problems like probabilistic inference, constraint satisfaction, query optimization, and matrix decomposition. The concept of tree decomposition was originally introduced by .
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 graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.
Glossary of graph theory
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
Related courses (3)
MATH-381: Mathematical logic
Branche des mathématiques en lien avec le fondement des mathématiques et l'informatique théorique. Le cours est centré sur la logique du 1er ordre et l'articulation entre syntaxe et sémantique.
CS-250: Algorithms
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma
MATH-683: Fine-grained and parameterized complexity
The classical distinction between polynomial time solvable and NP-hard problems is often too coarse. This course covers techniques for proving more fine-grained lower and upper bounds on complexity of
Related lectures (4)
Graph Theory and Network Flows
Introduces graph theory, network flows, and flow conservation laws with practical examples and theorems.
Edge Elimination and Orientation in Graphs
Covers edge elimination and orientation in graphs, including first order tests and logical orientation.
Networks: Structure and Properties
Explores the structure and properties of networks, including dating and protein networks, small-world effect, hubs, and scale-free property.