# Correspondence between Multilevel Graph Partitions and Tree Decompositions
## 4 Correspondence between Multilevel Graph Partitioning and Tree Decompositions
### Bijection Proof
Lemma 10: _Given a rooted tree decomposition with leaf and small bag properties and the multilevel partition constructed by TD2 MLP, for every non-root bag \(X\) with parent bag \(X_{p}\) and corresponding cell \(C\), the boundary of \(C\) is equal to \(X\cap X_{p}\), i.e., \(X\cap X_{p}=B_{C}\)._  
**Proof. ** Denote by \(X\) a bag and by \(C\) the cell constructed by TD2 MLP. \(C\) is constructed by TD2 MLP as \((\bigcup\mathcal{X}_{d})\setminus(X\cap X_{p})\) where \(X_{p}\) is the parent of \(X\) and \(\mathcal{X}_{d}\) is the set descendant bags of \(X\). We prove \(X\cap X_{p}=B_{C}\) by showing that \(\forall x:x\in X\cap X_{p}\implies x\in B_{C}\) and \(\forall x:x\in B_{C}\implies x\in X\cap X_{p}\). We start with an \(x\in X\cap X_{p}\). We need to show that \(x\in B_{C}\). Using Lemma 9, we know that an edge \(\{x,y\}\) and a bag \(Y\) exists such that \(x\in Y\), \(y\in Y\) and \(y\
ot\in X_{p}\). As \(Y\) is a descendant of \(X\), \(Y\subseteq\bigcup\mathcal{X}_{d}\). Further, as \(y\
ot\in X_{p}\), \(y\) is not in \(X\cap X_{p}\). \(y\) is therefore in \(C\). \(x\) is not in \(C\). As \(\{x,y\}\) is an edge, \(x\) is on the boundary of \(C\), i.e., \(x\in B_{C}\). Next, we start with an \(x\in B_{C}\). We need to show that \(x\in X\cap X_{p}\). As \(x\in B_{C}\), there must exist an edge \(\{x,y\}\) such that \(y\in C\). From the edge requirement follows, that a bag \(Y\) must exist that contains both \(x\) and \(y\). As \(y\in C\), \(y\) is either not in \(X\) or not in \(X_{p}\). In either case, it follows that \(Y\) is a descendantbag of \(X\). As \(x\in Y\), it follows that \(x\in\bigcup\mathcal{X}_{d}\). As \(x\in B_{C}\), \(x\) is not part of \(C\). \(x\) must therefore be in \(X\cap X_{p}\). Given a rooted tree decomposition with leaf property and the multilevel partition constructed by TD2 MLP, for every non-root bag \(X\) with parent bag \(X_{p}\) and corresponding cell \(C\), the separator of \(C\) is equal to \(X\setminus X_{p}\), i.e., \(X\setminus X_{p}=S_{C}\). Denote by \(X\) a bag and by \(C\) the cell constructed by TD2 MLP. We prove \(X\setminus X_{p}=S_{C}\) by showing that \(\forall x:x\in X\setminus X_{p}\implies x\in S_{C}\) and \(\forall x:x\in S_{C}\implies x\in X\setminus X_{p}\). Start with a node \(x\in X\setminus X_{p}\). We need to show that \(x\in S_{C}\). As \(X\) is a descendant of itself, \(x\in C\). Denote by \(Y\) a child of \(X\) and by \(D\) the corresponding cell. \(D\) is defined as \((\bigcup\mathcal{Y}_{d})\setminus(Y\cap X)\). As \(x\in X\), \(D\) cannot contain \(x\). As no child cell can contain \(x\) and \(x\in C\), \(x\) must in the separator \(S_{C}\). Next, we start with a node \(x\in S_{C}\). We need to show that \(x\in X\setminus X_{p}\). We first show \(x\in X\) and then \(x\
ot\in X_{p}\). As \(x\in S_{C}\), we know that \(x\in C\). As \(x\in C\) and \(C=(\bigcup\mathcal{X}_{d})\setminus(X\cap X_{p})\), \(x\) must be part of a descendant bag \(Y\) of \(X\). If \(Y=X\), we have shown that \(x\in X\). Otherwise, denote by \(D\) the cell corresponding to \(Y\). As \(x\) is in the separator of \(C\), \(x\) cannot be in \(D\). As \(D=(\bigcup\mathcal{Y}_{d})\setminus(Y\cap Y_{p})\) and \(x\in Y\), we conclude that \(x\) is in \(Y\cap Y_{p}\). \(x\) must thus also be in \(Y_{p}\). If \(Y_{p}=X\), we have shown that \(x\in X\). Otherwise, we repeat the argument for the cell corresponding to \(Y_{p}\) and conclude that \(x\) is part of the parent bag of \(Y_{p}\). As \(Y\) is a descendant of \(X\), we conclude that \(x\in X\), by applying this argument iteratively. Next, we show that \(x\
ot\in X_{p}\). If \(x\) was also in \(X_{p}\), \(x\) would be in \(X\cap X_{p}\). \(x\) would thus not be in \(C\). However, \(x\) is in \(C\) and therefore \(x\) is not part of \(X_{p}\). As \(x\in X\) and \(x\
ot\in X_{p}\), we conclude that \(x\in X\setminus X_{p}\). Let \(T\) be a rooted tree decomposition with leaf and small bag properties. Further, let \(T^{\prime}\) be the rooted tree decomposition obtained by applying TD2 MLP followed by MLP2 TD to \(T\).