# Correspondence between Multilevel Graph Partitions and Tree Decompositions
## 2 Tree Decomposition  
We denote by \(G=(V,E)\) an undirected graph. \(G\) has neither multiedges nor loops. Throughout this paper, we require that \(G\) is not empty. All tree decompositions and multilevel partitions are computed with respect to the same given graph \(G\). \(G\) is never modified in this paper. All stated modifications and constructions refer to a multilevel partition or a tree decomposition of \(G\).  
A _tree decomposition_ is a tree \(T\) with node multiset \(\mathcal{X}\). The tree \(T\) is called _backbone_ and its nodes are called _bags_. A bag is set of nodes of graph \(G\). Every tree decomposition must fulfill the following requirements:  
1. For every node \(u\in V\), there is a bag \(X\in\mathcal{X}\) such that \(u\in\mathcal{X}\).
2. For every edge \(\{u,v\}\in E\), there is a bag \(X\in\mathcal{X}\) such that \(u\in X\) and \(v\in X\).
3. For every pair of bags \(X\in\mathcal{X}\) and \(Y\in\mathcal{X}\), every bag \(Z\) along the unique path in \(T\) from \(X\) to \(Y\) must contain the intersection of \(X\) and \(Y\), i.e., \(X\cap Y\subseteq Z\).  
In this paper, we refer to them as _node_, _edge_, and _path requirements_. Without loss of generality, we assume throughout this paper that there are at least two bags.  
The width \(w(T)\) of a tree decomposition \(T\) is the maximum bag size minus one, i.e., \(w(T)=\max_{x\in X}|x|-1\). In most settings, tree decompositions of small width are desired. The minimum width of any tree decomposition is the _tree width_ of a graph \(G\).  
A _rooted_ tree decomposition additionally has a root bag \(X_{r}\). With respect to a root bag, every bag \(X\) except the root itself has a parent bag \(X_{p}\). A bag is a _child_ of its parent bag. Similarly, a bag \(Y\) is a _descendant_ of \(X\), if \(X\) is on the path from \(Y\) to the root. \(X\) is a descendant of \(X\). We denote by \(\mathcal{X}_{d}\) a set of descendant bags. A bag without children is a _leaf bag_. As we assumed that there are at least two bags, the root bag is never a leaf bag.  
To establish a one-to-one correspondence with multilevel partitions, we require two additional technical requirements:  
1. no leaf bag is a subset of its parent bag; and
2. for every non-root bag \(X\) and node \(x\in X\), such that the parent bag but no child bag of \(X\) contains \(x\), removing \(x\) from \(X\) must result in a violation of the edge property.  
In this paper, we refer to the fourth property as _leaf property_ and the fifth property as _small bag property_.  
Luckily, a rooted tree decomposition that does not fulfill the leaf property can easily be transformed into one that does by removing the offending leaf bags. Similarly, by removing offending nodes, a tree decomposition can be constructed that fulfills the small bag property. Important metrics such as the width of a tree decomposition cannot be increased by these transformations. Both properties thus only codify that a certain class of superfluous bags and nodes must not exist.  
In Figure 1, we present an example tree decomposition that we use as running example throughout this paper. The first tree decomposition property requires that for every edge in \(G\) there is a bag \(x\) in \(T\) that contains both endpoints. For example, the endpoints of the edge \(\{g,p\}\) are contained in the bag \(\{f,g,p,c\}\). The property does not require that the bag is unique. For example, the endpoints of the edge \(\{m,o\}\) are contained in two bags, namely \(\{o,m,p\}\) and \(\{n,o,m\}\). The third tree decomposition property requires that every node in the intersection of two bags is in every bag between them. For example, \(p\) is part of the bags \(\{f,m,p\}\) and \(\{p,r,i\}\). The property requires that \(p\) is also part of the bags on the path between. These are \(\{f,p,c\}\), \(\{p,c\}\), and \(\{p,c,i\}\).