# Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies
## 2 Materials and Methods
### FlowCutter  
FlowCutter is an algorithm for the balanced graph bipartitioning problem. The idea of its _core algorithm_ is to solve a sequence of incremental max flow problems, which induce cuts with monotonically increasing cut size and balance, until the latest cut induces an \(\varepsilon\)-balanced bipartition. The flow problems are incremental in the sense that the terminal nodes \(S,T\) of the previous flow problem are subsets of the terminals in the next flow problem. This nesting allows us to reuse the flow computed in previous iterations.  
Given randomly chosen starting terminal nodes \(s,t\), we set \(S:=\{s\},T:=\{t\}\) and compute a maximum \(S\)-\(T\) flow. Then, we transform the \(S\)-reachable nodes \(S_{r}\) to sources if \(|S_{r}|\leq|T_{r}|\), or \(T_{r}\) to targets otherwise. Assume \(|S_{r}|\leq|T_{r}|\) without loss of generality. Now \(S\) induces a minimum \(S\)-\(T\) cut \(C_{S}\). If \(C_{S}\) is \(\varepsilon\)-balanced, the algorithm terminates. Otherwise, we transform one additional node, called _piercing node_, to a source. The piercing node is chosen from the nodes incident to the cut \(C_{S}\) and not in \(S\). This step is called _piercing_ the cut \(C_{S}\). It ensures that we will find a different cut in the next iteration. Subsequently, we augment the previous flow to a maximum flow that considers the new source node. These steps are repeated until the latest cut induces an \(\varepsilon\)-balanced bipartition. Algorithm 1 shows pseudocode for FlowCutter.  
```
1 Draw \(s,t\in V\) uniformly at random and let \(S\leftarrow\{s\},T\leftarrow\{t\}\)
2 Let \(f:A\rightarrow\{-1,0,1\}\), \(a\ \mapsto 0\)
3 whileno \(\varepsilon\)-balanced bipartition founddo
4 update \(f\) to a max \(S\)-\(T\) flow and compute \(S_{r},T_{r}\)
5 if\(|S_{R}|\leq|T_{R}|\)then
6\(S\gets S_{r}\)
7 derive and report source-side cut \(C_{S}\)
8 select piercing nodes \(p\) for \(C_{S}\)
9\(S\gets S\cup\{p\}\)
10 else
11\(T\gets T_{r}\)
12 derive and report target-side cut \(C_{T}\)
13 select piercing node \(p\) for \(C_{T}\)
14\(T\gets T\cup\{p\}\)
```  
**Algorithm 1**FlowCutter  
A significant detail of the piercing step is that piercing nodes which are not reachable from the opposite side are preferred. Choosing such nodes for piercing does not create augmenting paths. Thus, the cut size does not increase in the next iteration. This is called the _avoid-augmenting-paths_ heuristic. A secondary _distance-based_ piercing heuristic is used to break ties, when the avoid-augmenting-paths heuristic gives multiple choices. It chooses the node \(p\) which minimizes \(\operatorname{dist}(p,t)-\operatorname{dist}(s,p)\), where dist is the hop distance, precomputed via Breadth-First-Search from \(s\) and \(t\). Roughly speaking, this attempts to prevent the cut sides from meeting before perfect balance. It also has a geometric interpretation, which is explained in [14].  
We choose the starting terminal nodes \(s\) and \(t\) uniformly at random. Experiments [14] indicate that 20 terminal pairs are sufficient to obtain high quality partitions of road networks.  
For computing maximum flows, we use the basic Ford-Fulkerson algorithm [20], with Pseudo-Depth-First-Search for finding augmenting paths. Pseudo-Depth-First-Search directly marks all adjacent nodes as visited when processing a node. It can be implemented like Breadth-First-Search using a stack instead of a queue.  
A major advantage of FlowCutter over other partitioning tools is the fact that it computes multiple cuts. From this set of cuts, we derive the _Pareto cutset_, which we define as the set of all nondominated cuts. A cut \(C_{2}\) is _dominated_ by a cut \(C_{1}\) if \(C_{2}\) has neither better balance nor smaller cut size than \(C_{1}\). Instead of selecting a maximum imbalance a priori, we can select a good trade-off between cut size and imbalance from the Pareto cutset.