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

Official source

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 publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related units

Related people

No results

No results

Related publications (5)

Loading

Loading

Loading

Related concepts (2)

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

Graph (discrete mathematics)

In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects corre

Related courses (3)

Related lectures (2)

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-328: Numerical methods for visual computing and ML

Visual computing and machine learning are characterized by their reliance on numerical algorithms to process large amounts of information such as images, shapes, and 3D volumes. This course will familiarize students with a range of essential numerical tools to solve practical problems in this area.

MGT-416: Causal inference

Students will learn the core concepts and techniques of network analysis with emphasis on causal inference. Theory and application will be balanced, with students working directly with network data throughout the course.

This paper's focus is the following family of problems, denoted k-ECSS, where k denotes a positive integer: given a graph (V, E) and costs for each edge, find a minimum-cost subset F of E such that (V, F) is k-edge-connected. For k=1 it is the spanning tree problem which is in P; for every other k it is APX-hard and has a 2-approximation. Moreover, assuming P != NP, it is known that for unit costs, the best possible approximation ratio is 1 + Theta(1/k) for k>1. Our first main result is to determine the analogous asymptotic ratio for general costs: we show there is a constant eps>0 so that for all k>1, finding a (1+eps)-approximation for k-ECSS is NP-hard. Thus we establish a gap between the unit-cost and general-cost versions, for large enough k. Next, we consider the multi-subgraph cousin of k-ECSS, in which we are allowed to buy arbitrarily many copies of any edges (i.e., F is now a multi-subset of E, with parallel copies having the same cost as the original edge). Not so much is known about this natural variant, but we conjecture that a (1 + Theta(1/k))-approximation algorithm exists, and we describe an approach based on its naive linear programming relaxation (LP) and graph decompositions. The LP is well-known --- it is essentially the same as the Held-Karp TSP and the undirected LP for Steiner tree --- and in order to further our understanding, we give a family of extreme points for this LP with exponentially bad fractionality.

This paper introduces a chordal decomposition approach for scalable analysis of linear networked systems, including stability, H 2 and H ∞ performance. Our main strategy is to exploit any sparsity within these analysis problems and use chordal decomposition. We first show that Grone's and Agler's theorems can be generalized to block matrices with any partition. This facilitates networked systems analysis, allowing one to solely focus on the physical connections of networked systems to exploit scalability. Then, by choosing Lyapunov functions with appropriate sparsity patterns, we decompose large positive semidefinite constraints in all of the analysis problems into multiple smaller ones depending on the maximal cliques of the system graph. This makes the solutions more computationally efficient via a recent first-order algorithm. Numerical experiments demonstrate the efficiency and scalability of the proposed method.

In a previous article, we have shown that adequate subgraphs can be used to decompose multiple breakpoint graphs, achieving a dramatic speedup in solving the median problem. In this article, focusing on the median of three problem, we prove more important properties about adequate subgraphs with rank 3 and discuss the algorithms inventorying simple adequate subgraphs. After finding simple adequate subgraphs of small sizes, we incorporate them into ASMedian, an algorithm to solve the median of three problem. Results on simulated data show dramatic speedup so that many instances can be solved very quickly, even ones containing hundreds or thousands of genes.