# Correspondence between Multilevel Graph Partitions and Tree Decompositions
## 4 Correspondence between Multilevel Graph Partitioning and Tree Decompositions
### Asymptotic Running Times  
The running times of MLP2 TD and TD2 MLP depend on detailed in-memory representations used for multilevel partitions and tree decompositions. We represent node-based multilevel partition cells in-memory by their separator. Additionally, we store the parent/child relationships among cells. This has the nice property that the amount of storage needed to represent any multilevel partition \(P\) is linear in the number of nodes of the graph and the tree. Each cell is the union of its children and its separator. Therefore, the nodes of each cell \(C\) can be recovered by a bottom-up traversal that builds the union of the separator of \(C\) and all children of \(C\). Our analysis assumes an implementation that stores a bag \(X\) as an array of node IDs. The tree backbone stores for every bag the parent bag's ID and an array of child bag IDs. Cells are represented as array containing the separator \(S_{C}\). Further, we store the parent and the children cell's IDs. In Algorithms 1 and 2, we present two recursive functions that implement MLP2 TD and TD2 MLP, respectively. We do not explicitly build a tree-backbone or the multilevel partition tree in these functions but just output bags or separators. As both trees are traversed recursively, it is however easy to build them. ```
Input: Root cell represented by separator \(S_{r}\)
1 Initialize all nodes as unmarked; OutputBags(\(S_{r}\));
2 FunctionOutputBags(\(S\)):
3 Boundary \(B\leftarrow\emptyset\);
4 for\(S_{c}\in children(S)\)do
5\(B\gets B\cup\texttt{OutputBags}(S_{c})\);
6 for\(u\in S\)do
7 mark \(u\);
8\(B\gets B\cup N(u)\);
9
10 Remove marked nodes from \(B\);
11 Output \(X=B\cup S\);
12 return\(B\);
```  
**Algorithm 1**Recursive function that implements MLP2 TD. For MLP2 TD, we need to calculate the boundary of each cell. OutputBags() in Algorithm 1 recursively calculates the boundary of each cell represented by a separator \(S\). It first calls itself on all children and accumulates their boundaries in \(B\). Then, it marks all nodes in the separator and adds their neighbors to \(B\). Note that marks are global and never cleared. The boundary is then obtained by removing all marked nodes from \(B\). By building the union of \(S\) and \(B\), it then outputs the corresponding bag \(X\). To show its correctness, we need to show that OutputBags indeed returns the boundary of the cell represented by \(S\). In Algorithm 1, OutputBags returns the boundary of the cell represented by \(S\). Proof. : The proof consists of three steps: First, we show that we obtain a suitable set of candidates on lines 4-9. Then, we show that line 10 removes all nodes that are not in the boundary. As a last step, we show that line 10 does not remove any nodes that are in the boundary. As a cell \(C\) is the union of the children of \(C\) and \(C\)'s separator, any node in the boundary of \(C\) must either be in the boundary of one of \(C\)'s children or a neighbor of a node of \(C\)'s separator. Therefore, after lines 4-9, \(B\) is a superset of the boundary. Further, any node that is in \(B\) but not in the boundary is part of \(C\). Due to the recursive calls of OutputBags, all separators of children of \(S\) are marked and thus at least all nodes in \(C\) are marked. Therefore, in line 10, all nodes of \(C\) are removed. What remains to be shown is that we have not marked too many nodes. Note that marks are never cleared. We only mark nodes that are contained in a cell that is processed. Thus, any node may be marked unless it is only contained in ancestors of \(C\). Any cell \(C_{b}\) that contains one of \(C\)'s boundary nodes touches \(C\) and is thus, according to the definition of multilevel partitions, either a descendant or an ancestor of \(C\). As \(C_{b}\) contains a node that is not in \(C\), it must be an ancestor of \(C\). Therefore, \(C_{b}\) is processed after \(C\). This means that no node of the boundary has been marked. The running time of Algorithm 1 is linear in the size of the graph and the tree decomposition it computes. Proof.