# Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies
## 3 Results
### Pareto Cut Experiments
\begin{table}
\begin{tabular}{c c c c c c c c c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Category**} & \multicolumn{10}{c}{**Achieved \(\varepsilon\) [\%]**} & \multicolumn{10}{c}{**Cut Size**} \\ \cline{2-13}  & **IFC4** & **IFC8** & **IFC12** & **F3** & **F20** & **K2.11** & **M** & **I** & **IFC4** & **IFC8** & **IFC12** & **F3** & **F20** & **K2.11** & **M** & **I** \\ \hline
0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & \(\downarrow\)0 & – & 0.0 & 57 & 46 & 46 & 80 & 43 & 46 & – & 306 \\
1 & 1.0 & 1.0 & 1.0 & 0.2 & 0.2 & 0.2 & 0.0 & 0.6 & 39 & 35 & 35 & 61 & 31 & 31 & 63 & 93 \\
3 & 2.3 & 2.3 & 2.3 & 2.4 & 2.3 & \(<\)0.1 & 1.1 & 29 & 29 & 29 & 50 & 29 & 29 & 51 & 64 \\
5 & 2.3 & 2.3 & 2.3 & 4.3 & 2.3 & 2.3 & \(<\)0.1 & 1.6 & 29 & 29 & 29 & 34 & 29 & 29 & 56 & 62 \\
10 & 2.3 & 2.3 & 2.3 & 5.3 & 2.3 & 2.3 & 0.3 & 0.6 & 29 & 29 & 29 & 29 & 29 & 29 & 44 & 37 \\
20 & 16.7 & 16.7 & 5.3 & 16.7 & 16.7 & \(<\)0.1 & 2.7 & 28 & 28 & 28 & 29 & 28 & 28 & 47 & 29 \\
30 & 16.7 & 16.7 & 5.3 & 16.7 & 2.3 & \(<\)0.1 & 5.5 & 28 & 28 & 28 & 29 & 28 & 29 & 50 & 29 \\
50 & 42.3 & 42.3 & 42.3 & 5.3 & 49.1 & 2.3 & 33.3 & 40.8 & 25 & 25 & 25 & 29 & 24 & 29 & 3118 & 27 \\
70 & 42.3 & 42.3 & 42.3 & 67.0 & 49.1 & 2.3 & 41.2 & 42.6 & 25 & 25 & 25 & 28 & 24 & 29 & 3343 & 26 \\
90 & 85.4 & 85.4 & 85.4 & 90.0 & 89.8 & 49.1 & 47.4 & 85.6 & 18 & 18 & 18 & 15 & 14 & 24 & 3040 & 18 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Pareto cuts of California and Nevada. KaHIP achieves exceptionally small, highly balanced cuts on the Europe road network. On the other road networks, it is similar to or worse than F20 in terms of cut size. This is due to the special geography of the Europe road network. It excludes large parts of Eastern Europe, which is why there is a cut of size 2 and \(\varepsilon=72.8\%\) imbalance that separates Norway, Sweden, and Finland from the rest of Europe. For \(\varepsilon=10\%\), KaHiP computes a cut with 112 edges, which separates the European mainland from the Iberian peninsula, Britain, Scandinavia minus Denmark, Italy, and Austria [14]. The Alps separate Italy from the rest of Europe. Britain is only connected via ferries, and the Iberian peninsula is separated from the remaining mainland by the Pyrenees. One side of the cut is not connected because the only ferry between Britain and Scandinavia runs between Britain and Denmark. FlowCutter is unable to find cuts with disconnected sides without a modified initialization. By handpicking terminals for FlowCutter, a similar cut with only 87 edges and 15% imbalance, which places Austria with the mainland instead, is found in [14]. However, it turns out that the FlowCutter CCH order using the 87 edge cut as a top-level separator is not much better than plain FlowCutter. This indicates that it does not matter at what level of recursion the different cuts are found. For large imbalances, KaHIP seems unable to leverage the additional freedom to achieve the much smaller but more unbalanced cuts, like the ones reported by InertialFlowCutter and FlowCutter. This has already been observed for previous versions of KaHIP [14]. In terms of running time, KaHIP and F20 are the slowest algorithms. InertialFlowCutter is in all three configurations an order of magnitude faster than F20. Up to a maximum \(\varepsilon\) of 10%, the three variants report almost the same cuts. Apart from the very imbalanced \(\varepsilon=90\%\) cuts, the cuts are also at most one edge worse than F20. Only for more balanced cuts more cutters give a significant improvement. Here, in particular on the Europe road network, F20 is also significantly better than InertialFlowCutter. In the range between \(\varepsilon=60\%\) and \(\varepsilon=10\%\), which is most relevant for our application, there is thus no significant difference between F20 and InertialFlowCutter, regardless of the number of cutters. This indicates that on the top level, the first four directions seem to cover most cuts already. On the other hand, for highly balanced