# Correspondence between Multilevel Graph Partitions and Tree Decompositions
## 4 Correspondence between Multilevel Graph Partitioning and Tree Decompositions
### Bijection Proof  
We have shown that the MLP2 TD and TD2 MLP algorithms are correct. It remains to show that the functions described by these algorithms form a bijection. We first show in Lemma 8 that the round trip is safe for multilevel partitions. Later, in Lemma 12, we show the same for tree decompositions. **Lemma 8**. : _Let \(\mathcal{C}^{\prime}\) be the multilevel partition obtained by applying MLP2 TD followed by TD2 MLP to the multilevel partition \(\mathcal{C}\). Both multilevel partitions are identical, i.e., \(\mathcal{C}^{\prime}=\mathcal{C}\)._  
**Proof. ** Our proof consists of two parts. We show separately that \(x\in C\implies x\in C^{\prime}\) and \(x\in C^{\prime}\implies x\in C\). We first show that \(x\in C\) implies \(x\in C^{\prime}\). Denote by \(C_{p}\) the parent cell of \(C\). As \(x\) is in \(C\), \(x\) is neither in the separator of \(C_{p}\) nor on the boundary of \(C_{p}\). \(x\) is therefore not in the bag of \(C_{p}\). As \(x\) is in \(C\), \(x\) is part of the separator of a descendant cell \(D\) of \(C\). \(x\) is therefore part of \(D\)'s bag. \(C^{\prime}\) is computed as the union of the descendant bags of \(C\)'s bag, which includes \(D\)'s bag, minus the intersection of \(C\)'s bag and \(C_{p}\)'s bag. As \(D\)'s bag includes \(x\) but \(C_{p}\)'s bag does not, it follows that \(x\in C^{\prime}\). Next, we show that from \(x\in C^{\prime}\) follows that \(x\in C\). Again, denote by \(C_{p}\) the parent cell of \(C\). From \(x\in C^{\prime}\), we know that \(x\) is in the union of \(C\)'s descendants' bags. \(x\) must therefore be in at least one of these bags. Denote by \(D\) the cell corresponding to this bag in the input multilevel partition. The bag of \(D\) is a subset of the union of \(C\) and \(C\)'s boundary. If we can show that \(x\) is not on the boundary of \(C\), then \(x\in C\) follows. By construction, we know that \(x\) is absent from the intersection of \(C\)'s bag with \(C_{p}\)'s bag. As \(x\) is in \(D\) and because of the path requirement of tree decompositions, we know that if \(x\) was in \(C_{p}\)'s bag it would also have to be in \(C\)'s bag. However, this is a contradiction with \(x\) being in the intersection of \(C\)'s bag with \(C_{p}\)'s bag. \(x\) is therefore no part of any bag that corresponds to a cell that is not a descendant of \(C\). \(x\) is therefore not on the boundary of \(C\). It follows that \(x\in C\). We have shown that every multilevel partition can be viewed as rooted tree decomposition. The question that remains is whether, every rooted tree decomposition can be viewed as multilevel partition. This only holds if the tree decomposition fulfills the leaf and small bag properties. Fortunately, every rooted tree decomposition can easily be transformed into one that has these properties. Our proof is organized in several lemmas. Lemma 9 formulates a direct consequence of the small bag property. This consequence is used in the proof of Lemma 10, which shows that \(X\cap X_{p}=B_{C}\) holds for multilevel partitions constructed by TD2 MLP. Similarly, Lemma 11 shows the same for \(X\setminus X_{p}=S_{C}\). Lemma 11 does not require the small bag property. Lemma 12 ties all these Lemmas together. Finally, from Lemmas 8 and 12, the main Theorem 1 directly follows. Lemma 9: _In a rooted tree decomposition with small bag property, for every non-root bag \(X\) and node \(x\) in \(X\cap X_{p}\), there exists a descendant bag \(Y\) and an edge \(\{x,y\}\) such that \(Y\) contains \(x\) and \(y\) but no bag that is not descendant of \(X\) contains \(y\)._  
**Proof. ** The small bag property states that \(x\) cannot be removed from all descendant bags of \(X\) without violating the edge requirement. An edge \(\{x,y\}\) must therefore exist such that \(x\) and \(y\) are part of a descendant bag \(Y\) of \(X\). Further, \(x\) and \(y\) cannot both be part of \(X_{p}\). As \(x\in X_{p}\), we conclude that \(y\
ot\in X_{p}\).