# Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies
## 3 Results
### Partitioner Implementations and Nested Dissection Setup  
In [14], the KaHiP versions 0.61 and 1.00 are used. We did not re-run the preprocessing for those old versions of KaHiP but used the orders and order computation running times of [14]. We did re-run customizations and queries. The order computation running times are comparable as the experiments ran on the same machine. We added the latest KaHiP version 2.11, which is available on GitHub [31]. For all three versions, the _strong_ preset of KaHiP was used. We refer to the three KaHiP variants as K0.61, K1.00, and K2.11. For the CCH order experiments, we kept versions K0.61 and K1.00 but omitted them for the top-level cut experiments because K2.11 is better for top-level cuts.  
We used Metis 5.1.0, available from the authors' website [32], which we denote by M in our tables.  
We used InertialFlowCutter with \(\langle 4,8,12,16\rangle\) directions and denote the configurations by IFC4, IFC8, IFC12, and IFC16, respectively.  
We used our own Inertial Flow implementation with the four directions proposed in [15]. It is available at our repository [28]. Instead of Dinic algorithm [33], we used Ford-Fulkerson, as preliminary experiments indicate it is faster. Furthermore, we filtered source nodes that are only connected to other sources and target nodes that are only connected to other targets. Instead of sorting nodes along a direction, we partitioned the node-array such that the first and last \(\alpha\cdot n\) nodes are the desired terminals, using std::nth_element. These optimizations reduce the running time from 1017 s [14] down to 450 s for a CCH order on Europe. Additionally, we used flow-based interleaving on Inertial Flow. This was already included in the Inertial Flow implementation used in [14]. We denote Inertial Flow by I in our tables.  
The original FlowCutter implementation used in [14] is available on GitHub [22]. We used a slightly modified version that has been adjusted to use Intel's Threading Building Blocks instead of OpenMP for optional parallelism. All parallelism is disabled for FlowCutter in our experiments. We used FlowCutter with \(\langle 3,20,100\rangle\) random source-target pairs and denote the variants by F3, F20, and F100, respectively.  
Implementations of Buffoon [19] and PUNCH [18] are not publicly available. Therefore, these are not included in our experiments.  
We now discuss the different node ordering setups used in the experiments. Metis offers its own node ordering tool ndmetis, which we used. For Inertial Flow, K1.00 and K2.11, we used a nested dissection implementation, which computes one edge cut per level and recurses until components are trees or cliques, which are solved directly. Separators are derived by picking the nodes incident to one side of the edge cut. For comparability with [12; 14], we used an older nested dissection implementation for K0.61, which, on every level, repeatedly computes edge cuts until no smaller cut is found for ten consecutive iterations. For InertialFlowCutter and FlowCutter, we employed the setup that was proposed for FlowCutter in [14] that has also been described in Section 2.7. Our nested dissection implementation is based on the implementation in the FlowCutter repository [22]. We made minor changes and parallelized it, as described in Section 2.8.  
We tried to employ the special preprocessing techniques for KaHiP 2.11. While this made order computation faster, the order quality was much worse regarding all criteria.  
Starting with version 1.00, KaHiP includes a more sophisticated multilevel node separator algorithm [34]. It was omitted from the experiments in [14] because it took 19 hours to compute an order for the small California graph, using one separator per level, and did not finish in reasonable time on the larger instances. Therefore, we still exclude it.