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 . 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.

Counting and Sampling from Markov Equivalent DAGs Using Clique Trees

Negar Kiyavash, Saber Salehkaleybar, Kun Zhang

A directed acyclic graph (DAG) is the most common graphical model for representing causal relationships among a set of variables. When restricted to using only observational data, the structure of the ground truth DAG is identifiable only up to Markov equi ...

AAAI Press2019

Distributed Design for Decentralized Control using Chordal Decomposition and ADMM

Counting and Sampling from Markov Equivalent DAGs Using Clique Trees

Counting and Sampling from Markov Equivalent DAGs Using Clique Trees

Distributed Design for Decentralized Control using Chordal Decomposition and ADMM