Graph Bisection with Pareto-Optimization∗
Michael Hamann, Ben Strasser

arXiv:1504.03812v3 [cs.DS] 22 Nov 2017

Institute of Theoretical Informatics,
Karlsruhe Institute of Technology,
P.O. Box 6980, 76128 Karlsruhe, Germany.

Abstract
We introduce FlowCutter, a novel algorithm to compute a set of edge cuts or node separators that optimize cut size and balance in the Pareto-sense. Our core algorithm heuristically
solves the balanced connected st-edge-cut problem, where two given nodes s and t must
be separated by removing edges to obtain two connected parts. Using the core algorithm
as subroutine, we build variants that compute node separators which are independent of s
and t. From the computed Pareto-set, we can identify cuts with a particularly good tradeoff between cut size and balance that can be used to compute contraction and minimum
fill-in orders, which can be used in Customizable Contraction Hierarchies (CCH), a speed-up
technique for shortest path computations. Our core algorithm runs in O(c|E|) time where
E is the set of edges and c is the size of the largest outputted cut. This makes it wellsuited for separating large graphs with small cuts, such as road graphs, which is the primary
application motivating our research. For road graphs, we present an extensive experimental study demonstrating that FlowCutter outperforms the current state-of-the-art both in
terms of cut sizes and CCH performance. By evaluating FlowCutter on a standard graph
partitioning benchmark, we further show that FlowCutter also finds small, balanced cuts
on non-road graphs. Another application is the computation of small tree-decompositions.
To evaluate the quality of our algorithm in this context, we entered the PACE 2016 challenge [13] and won the first place in the corresponding sequential competition track. We
can therefore conlude that our FlowCutter algorithm finds small, balanced cuts on a wide
variety of graphs.

1

Introduction

A graph cut is a set of edges, whose removal separates a graph into two sides. Similarly, a node
separator is a set of nodes whose removal separates a graph into two sides. A cut or separator is
balanced if the number of nodes in both sides is roughly the same. Balanced graph bisection is
the problem of finding a balanced cut or separator. This is a fundamental and NP-hard [24] graph
problem that has received a lot of attention [34, 16, 39, 2, 42] and has many applications. We
present FlowCutter, a novel algorithm to compute edge cuts and node separators. It computes
a set of cuts or separators that trade-off cut respectively separator size for imbalance in the
Pareto-sense. For edge cuts, FlowCutter guarantees that the two sides of the cut are connected
subgraphs. Experimentally, we show that the computed cuts and separators have a good quality.
However, as the problem is NP-hard, we cannot prove that the cuts and separators found are
always small. The application motivating our research is accelerating shortest path computations
in roads graphs [43, 30, 15, 3, 19]. The main part of our paper sticks with this application and
we demonstrate the usefulness of our proposed graph bisection algorithm directly by applying it
∗

Partial support by DFG grant WA654/19-1, WA654/22-1, and Google Focused Research Award.

1

in the context of shortest path computations. However, our proposed algorithm is not specific
to road graphs. We present experiments on graphs from other applications to demonstrate this.
Earlier versions of our work have been uploaded to ArXiv [28] and presented at the ALENEX
2016 conference [29].
Contribution We introduce FlowCutter, a graph bisection algorithm that optimizes cut size
and imbalance in the Pareto sense. The core FlowCutter algorithm aims to solve the balanced
edge-st-cut graph bisection problem with connected sides. Using this core as subroutine we
design algorithms to solve the node separator and non-st variants. Using these we design a
nested dissection-based algorithm to compute contraction node orders as needed by Customizable
Contraction Hierarchies (CCH) [19]. We prove that the core algorithm’s running time is in
O(c|E|) where E is the set of edges and c the size of the largest cut found. We show in an
extensive experimental evaluation that FlowCutter is a good fit for road graphs, as road graphs
tend to be large in terms of edge count but small in terms of cut size. We further show that
FlowCutter also finds small, balanced cuts on non-road graphs by comparing the cuts found by
FlowCutter to the state-of-the-art cuts on the benchmark set maintained by Chris Walshaw [44].
Finally, we demonstrate the performance of our algorithm on a broad class of graphs, by entering
and winning the corresponding sequential competition track of PACE 2016 tree-decomposition
challenge.
Outline Section 2 presents an overview of related work and the core ideas of the shortest path
application driving our research as well as some other applications including tree-decompositons.
Section 3 presents our notation and an overview of flows, CCH, tree-decompositions, separators,
and cuts and how some of these concepts relate to another. Section 4 introduces the core
FlowCutter st-bisection algorithm. Section 5 extends the core algorithm to general bisection,
node bisection, and describes how to compute CCH contraction orders. Section 6 presents an
extensive experimental evaluation on road graphs against the current state of the art and on the
well-known Walshaw benchmark for graph partitioning.

2

Applications and Related Work

We start by giving an overview of the core ideas employed to accelerate shortest path computations, illustrating how to apply the main topic of this work, which is graph bisection, to this
application. We limit this overview to the works immediately relevant to graph bisection and
refer readers interested in further details to a recent survey article [3].
Dijkstra’s algorithm [20] solves the shortest path problem in near-linear running time. However, this is not fast enough if the graph consists of a whole continent’s road network. Acceleration techniques usually compute auxiliary data in a preprocessing phase and compute the
shortest paths in a query phase. This auxiliary data is independent of the path’s endpoints
and can therefore be reused for many shortest path computations. As roads only change slowly
over time, the preprocessing phase can be slow as it does not have to be rerun very frequently.
Computing the auxiliary data usually involves optimizing some criteria, which most of the time
is NP-hard [4]. In this application, it is therefore important to produce solutions of good quality
but it is not as important to do this fast. Trading running time in the preprocessing phase for an
improvement of the auxiliary data is therefore most of time worthwhile. Some techniques such
as [15, 19] split the preprocessing phase and introduce a customization phase. In the preprocessing phase only the graph but not its weights are known. The weights are introduced in the
customization phase. The idea behind this setup is to be able to adapt more quickly to changes
in the weights, which could for example be caused by traffic congestion.
In many shortest path acceleration techniques, the preprocessing phase involves computing
balanced graph edge cuts or node separators. The central idea can be formulated in terms of
2

edge cuts as well as node separators. We present the node separators variant as we will evaluate
our bisection algorithms using Customizable Contraction Hierarchies (CCH) [19], an accelerating
technique based on the separator variant. However, many acceleration techniques, such as [15],
are based upon the edge cut variant. The idea can be described as follows: Given a graph G
and a node separator S, the algorithms precompute for every node in the graph how to get to
every node in S. Further, they precompute the shortest paths among all nodes of S. Consider
a query that asks to compute a shortest path from a node s to a node t. Either s and t are
on the same or on opposite sides of S. If they are on opposite sides, a shortest path can be
assembled by iterating over all nodes v in S and combining the precomputed paths from s to
v and from v to t and picking the shortest path. The running time of a distance query in this
case is thus in O(|S|), which is assumed to be small for road graphs. However, if s and t are on
the same side then a graph search is necessary using, for example, Dijkstra’s algorithm. On the
side of s and t the search is unrestricted. However, it does not cross S and instead makes use of
the shortest paths precomputed between the nodes of S. If the sides are of the same size and s
and t are chosen uniformly at random then there is a 50% probability that they are on opposite
sides. Half of the queries can therefore be answered quickly. For the other half of queries, this
approach restricts the search to half of the graph. However, as half of a continent is still large,
one usually applies this idea recursively.
The effectiveness of these techniques crucially depends on the size of the separators found.
The balance is less important. Perfect balance is not necessary to assure that the recursion
has a logarithmic depth. This application does, however, not benefit from a perfect balance.
In practice, the contrary is true: Requiring perfect balance results in many small, slightly
imbalanced separators not being found. Therefore, the perfectly balanced separators found can
be larger. This larger size is detrimental to the running time of the query phase, compared to
using the smaller slightly imbalanced separators. Fortunately, road graphs have small separators
and cuts because of geographical features such as rivers or mountains. Previous work has coined
the term natural cuts for this phenomenon [16]. However, identifying these natural cuts is a
difficult problem.
Graph partitioning software used for road graphs include KaHip [39], Metis [34], InertialFlow
[42], and PUNCH [16]. We experimentally compare FlowCutter with the first three. As we
unfortunately have no implementation of PUNCH, we omitted an experimental comparison with
it. All of these works formalize the graph bisection problem as a bicriteria problem optimizing
the cut size and the imbalance. The imbalance measures how much the sizes of both sides differ
and is small if the sides are balanced. The standard approach is to bound the imbalance and
minimize the cut size. However, this approach has several shortcomings. Consider a graph with a
million nodes and set the maximum imbalance to 1%. Suppose an algorithm finds a cut C1 with
180 edges and 0.9% imbalance. This is all the information of the cut’s quality that is provided.
Can you decide solely based on this information, whether this is a good cut? It seems good as
180 is small compared to the node count. However, we would come to a different conclusion, if
we knew that a cut C2 with 90 edges and 1.1% imbalance existed. In our application — shortest
paths — moving a few nodes to the other side of a cut is no problem. However, halving the
cut size has a huge impact. The cut C2 is thus clearly superior. Further, assume that a third
cut C3 with 180 edges and 0.7% imbalance existed. C3 dominates C1 in both criteria. However,
both are equivalent with respect to the standard problem formulation and thus a program is
not required to output C3 instead of C1 . To overcome these problems, our approach computes
a set of cuts that optimize cut size and imbalance in the Pareto sense, i.e., it tries to compute
solutions that are Pareto-optimal. As this problem is NP-hard, one cannot expect to always find
the exact Pareto curve. A further significant shortcoming of the state-of-the-art partitioners,
with the exception of InertialFlow, is that they were designed for small imbalances. Common
benchmarks, such as the one maintained by Chris Walshaw [44], only include test cases with
imbalances up to 5%. However, for our application imbalances of 50% can be fine. For such

3

high imbalances unexpected things happen with the standard software, such as increasing the
allowed imbalance can increase the achieved cut sizes. Indeed, KaHip, one of the competitors,
has been updated, as reaction to the conference version of our work [29], to overcome some of
these shortcomings. The newer version produces better results for higher imbalances than the
old version.
We use Customizable Contraction Hierarchies (CCH) [19] to evaluate the quality of the
separators found by FlowCutter. We present a more detailed CCH-overview in Section 3.3. The
CCH-auxiliary data at its core is a chordal supergraph of the road graph. The maximum cliques
of G0 , which can be efficiently identified in chordal graphs, correspond to the bags of a treedecomposition. This connection gives us a bridge to the vast field of tree-decomposition theory.
In Section 3.4, we give a high-level overview of the concepts related to tree-decompositions and
CCH. For a more in-depth survey we refer to [7], [8] and [9]. In some works tree-decompositions
are also called clique-trees.
Other Applications A vast amount of algorithms for NP-hard graph problems exist that are
fixed-parameter tractable in the tree-width of a graph G [12, 9]. It is therefore an interesting
question whether algorithms being able to compute good tree-decompositions in practice leads to
practicable variants of these algorithms. To investigate this question, the PACE competition [13]
was held in 2016 at IPEC, a conference with a focus on fixed-parameter tractable algorithms.
The objective of two competition tracks was to compute a small tree decomposition within a
limited time frame. The tracks differed in whether parallelism was allowed or not. To evaluate
the performance of FlowCutter in this context, we submitted our algorithm. Our implementation
runs FlowCutter iteratively with varying parameters until the time limit is reached. The parallel
version runs several FlowCutter instances in parallel. The code submitted to the PACE challenge
is open source and available at [45]. In the sequential track our implementation won the first
place out of six submissions and in the parallel track it won the second place out of 3 submissions.
Given these results, it is safe to say, that our algorithm is at least highly competitive, if not the
state-of-the-art, in terms of computing tree decompositions in practice.
The contraction orders used by CCH, which as based upon nested dissection [25, 36], are also
called minimum fill-in orders in the context of sparse matrices. This establishes a connection to
the theory of quickly solving sparse systems of linear equations. Indeed, METIS was developed
with this application in mind [34]. METIS was not developed to bisect road graphs. The fact that
we use METIS in the context of road graphs is therefore an example of this theoretical connection
being exploited in practice. Using the same connection, it is also possible to use FlowCutter
to solve sparse system of linear equations. However, even though these two applications are
so closely related, the precise trade-off between the various optimization criteria differs. For
example in the context of sparse equation systems, cut size is less important than in the road
setting whereas having a small bisection algorithm running time is more important.
Another application is information propagation in belief networks [32]. In this setting, a set
of random variables is given. It is known how these random variables depend on each other and
their interactions are modeled as a graph whose nodes are the random variables. The question is
how the distributions change throughout the graph if the distribution of a subset of the variables
changes, i.e., some but not all variables are measured. To solve this problem, so called junctiontrees are employed. Junction-trees are essentially another name for tree-decompositions. As we
can use FlowCutter to compute tree-decompositions, we can also use it to compute junctiontrees.

3

Preliminaries

A directed graph is denoted by G = (V, A) with node set V and arc set A ⊆ V × V . Similarly,
an undirected graph is denoted by G = (V, E) with node set V and edge set E ⊆ {e ∈ 2V :
4

|e| = 2}. Arcs have an implicit direction, whereas edges are undirected. A directed graph
is symmetric, if for every arc (y, x) there exists an arc (x, y). In a slight abuse of notation,
we do not discern between undirected and directed, symmetric graphs. We identify an edge
{x, y} with the corresponding pair of arcs (x, y) and (y, x). We set n := |V | and m := |A|.
As input, we only consider undirected graphs without multi-edges and without reflexive loops,
i.e., without arcs of the form (x, x). Road graphs that do not fit this description are modified1
by removing multi-edges, removing reflexive loops, and adding backarcs in the case of one-way
streets. In intermediate steps of our algorithm, we also consider non-symmetric directed graphs.
The out-degree do (x) of a node x is the number of outgoing arcs. Similarly, the in-degree di (x)
is the number of incoming arcs. In symmetric graphs, we refer to the value as degree d(x)
of x, as di (x) = do (x). A degree-2-chain is a sequence of adjacent nodes x, y1 . . . yk , z in a
symmetric graph such that k ≥ 1, d(x) 6= 2, d(z) 6= 2, and ∀i : d(yi ) = 2. An xy-path P is a
list (x, p1 ), (p1 , p2 ) . . . (pi , y) of adjacent arcs and i + 1 is P ’s length. The distance dist(x, y) is
defined as the minimum length over all xy-paths.

3.1

Cuts and Separators

A cut (V1 , V2 ) is a partition of V into two disjoint sets V1 and V2 such that V = V1 ∪ V2 . An
arc (x, y) with x ∈ V1 and y ∈ V2 is called cut-arc. In another slight abuse of notation, we do
not discern between the node partition and the set of cut-arcs. The size of a cut is the number
of cut-arcs. A min-cut is a cut of minimum size. A separator (V1 , V2 , Q) is a partition of V into
three disjoint sets V1 , V2 and Q such that V = V1 ∪ V2 ∪ Q. There must be no arc between
V1 and V2 . The cardinality of Q is the separator’s size. The imbalance  of a cut or separator
is defined as the smallest number such that max {|V1 | , |V2 |} ≤ d(1 + )n/2e. The imbalance of
a separator is defined analogously. For edge cuts 0 ≤  ≤ 1 holds. This is not necessarily the
case for node separators. The separator itself may contain nodes, making it possible that the
minimum  is smaller than 0, as both sides can have fewer than n/2 nodes. An ST -cut/separator
is a cut/separator between two disjoint node sets S and T such that S ⊆ V1 and T ⊆ V2 . If
S = {s} and T = {t}, we write st-cut/separator. The expansion of a cut/separator is the cut’s
size divided by min{|V1 | , |V2 |}.
Pareto-Optimization and NP-hardness Computing cuts (and separators) is inherently a
bicriteria problem: We want to minimize the cut size and minimize the imbalance. A cut C1
dominates a cut C2 if C1 is strictly better with respect to one criterion and no worse with respect
to the other criterion. A cut that is not dominated by any other cut is Pareto-optimal. We refer
to the pair of imbalance and cut size of a Pareto-optimal cut as Pareto-trade-off. It is possible
that several Pareto-optimal cuts exist with the same trade-off. The problem we consider asks
to compute one cut for every Pareto-trade-off. If there are several, then the algorithm is free to
pick any one of them.
This is a departure from existing experimental papers [34, 44, 39, 2, 14, 47, 42] that consider
the problem of finding a smallest cut subject to an imbalance bounded by an input parameter.
Given a cut for every Pareto-trade-off, it is easy to find a smallest cut with a bounded imbalance.
However, a cut with minimum size with an imbalance bounded by an input parameter is not
necessarily Pareto-optimal: It is possible that a more balanced cut with the same size exists.
Our problem setting is therefore a strict generalization of the problem setting considered in
previous works.
The minimum cut problem disregarding the imbalance is solvable in polynomial time [21].
However, nearly all cut-problems that combine optimizing imbalance and cut size are NP-hard.
Examples include:
1

As shown in the CCH-paper [19], this simplification does not hinder the applicability of CCH to directed
graphs.

5

• Finding a perfectly balanced minimum cut, i.e., one with  = 0, is NP-hard [24].
• A sparsest cut C is a cut that minimizes
a sparsest cut is NP-hard [35].

|C|
|V1 |·|V2 | .

A sparsest cut is Pareto-optimal. Finding

• Even computing, for a fixed st-pair, a most balanced cut among all st-cuts of minimum
size is already NP-hard [11].
• In [46], it was shown that computing a minimum cut that respects a given imbalance is
NP-hard.
Being able to compute a cut for every Pareto-trade-off efficiently would yield an efficient algorithm for all these NP-hard problems. Unless P=NP, we can therefore not hope to find
an efficient algorithm that provably computes an optimal cut for every Pareto-trade-off. Our
algorithm tries to heuristically compute in a single run a cut for every Pareto-trade-off.

3.2

Flows

In this paper we only consider unit flows. These are a restricted variant of the flow problem: Every arc has capacity 1 and an integral flow intensity of either 0 or 1. Formally,
a flow is a function f : A → {0, 1}. An arc a with f (a) = 1 is saturated. Denote by
P
P
p(x) = (x,y)∈A f (x, y) − (y,x)∈A f (y, x) the surplus of a node x. A flow is valid with respect to a source set S and target set T if and only if:
• Flow may be created at sources, i.e., ∀s ∈ S : p(s) ≥ 0,
• flow may be removed at targets, i.e., ∀t ∈ T : p(t) ≤ 0,
• flow is conserved at all other nodes, i.e., ∀x ∈ V \(S ∪ T ) : p(x) = 0,
• and flow does not flow in both directions, i.e., for all (x, y) ∈ A such that (y, x) ∈ A exists,
it holds that f (x, y) = 0 ∨ f (y, x) = 0.
The flow intensity is defined as the sum over all f (x, y) for arcs (x, y) with x ∈ S and y 6∈ S.
In other works, the flow intensity is sometimes also called flow value. A path a1 , a2 . . . , ai is
saturated if there exists an i with f (ai ) = 1. A node x is source-reachable if a non-saturated
sx-path exists with s ∈ S. Similarly, a node x is called target-reachable if a non-saturated
xt-path exists with t ∈ T . We denote by SR the set of all source-reachable nodes and by TR
the set of all target reachable nodes. In [21] it was shown that a flow is maximum, if and only
if no non-saturated st-path with s ∈ S and t ∈ T exists. If such a path exists, then it is called
augmenting path. The classic approach to compute max-flows consists of iteratively searching for
augmenting paths. Our algorithm builds upon this classic approach. The minimum ST -cut size
corresponds to the maximum ST -flow intensity. We define the source-side cut as (SR , V \SR )
and the target-side cut as (TR , V \TR ). Note that in general max-flows and min-cuts are not
unique. However, the source-side and target-side cuts are. The source-side and target-side cuts
are the same for every max-flow. The later is an implication of Corollary 5.3 of [22], which states
that every min-cut is saturated with respect to every max-flow.

3.3

Customizable Contraction Hierarchy

A Customizable Contraction Hierarchy (CCH) is an acceleration algorithm for shortest path
computations. We only give a high-level overview, as we use CCH only to evaluate the quality
of our separators. No part of FlowCutter builds upon CCH. The CCH details are in explained
in [19]. The technique uses three phases, i.e., a preprocessing phase, a customization phase, and
a query phase. In the preprocessing phase, the arc weights are unknown. These are integrated
into the auxiliary data in the customization phase. Shortest paths are computed in the query
phase.
6

Preprocessing The name-giving operation is the node contraction: Contracting a node v
consists of removing v and adding edges between all of v’s neighbors, if they did not already exist.
The input to CCH consists of a node contraction order along which the nodes are iteratively
contracted. This yields a supergraph G0 of the input graph. By convention, we say for every
edge {x, y} where x is contracted before y, that x is lower than y. The position of a node in the
order is called rank.
Customization The weights of G0 are computed using an algorithm that essentially enumerates all triangles in G0 . Initially, all edges of G0 already present in G are assigned their input
weights, whereas all edges introduced during the contraction are giving the weight ∞. The algorithm then enumerates all triangles {x, y, z} in G0 ordered increasingly by the position of the
lowest node in the triangle. Suppose that z is this lowest node. For each triangle the algorithm
executes w(x, y) ← min{w(x, y), w(x, z) + w(z, y)}. As shown in [19], for every pair of nodes s
and t there is a shortest st-up-down-path after the customization has finished. This is a path
with nodes v1 . . . vm . . . v` such that the nodes v1 . . . vm appear ordered increasingly by rank and
the nodes vm . . . v` appear ordered decreasingly by rank. The nodes v1 . . . vm form the upward
part of the path and the nodes vm . . . v` form the downward part.
Query Given the weights of G0 , the shortest path query consists of a bidirectional search in
G0 . Both the forward and the backward searches follows only upward arcs (x, y) such that x has
a lower rank than y. The forward search finds the upward part and the backward search the
downward part of a shortest st-up-down-path. The search space of a node z is the subgraph of
G0 that is reachable from z while only following upward arcs. The query therefore only explores
at most the whole search spaces of s and t.
Performance Smaller search spaces yield faster queries. Fewer triangles in G0 yield a faster
customization. Fewer edges in G0 result in less memory consumption. All these quality metrics
depend on the contraction order.
We compute contraction orders using nested dissection [25, 36], which works as follows: (1)
Determine a small balanced separator S, (2) recursively compute orders L and R for both sides,
(3) the contraction order of G consists of first contracting the nodes along L, then R, and finally
along an arbitrary order of the nodes in S. The quality of the so obtained contraction order
depends on the quality of the separators used in its construction. Finding these separators is
where FlowCutter fits into the big picture.

3.4

Tree-Decompositions

We present an overview of the theory of tree-decompositions. As the sheer quantity of works
written on this subject makes it impossible to introduce them all, we refer the interested reader
to three survey articles [7, 8, 9].
Definition A tree-decomposition of an undirected graph G = (V, E) is a pair (B, T ) where B
is a set of subsets of V . The elements of B are called bags. Every bag is a set of nodes. The
union of all bags must equal V . It is required that for every {x, y} ∈ E there is a bag b ∈ B
such that x ∈ b and y ∈ b, i.e., every edge is in one or more bags. T is a tree with the elements
of B as nodes. T is called the backbone of the decomposition. Finally, it is required that for
every pair of bags bs and bt whose intersection contains a vertex v ∈ bs ∩ bt , that all bags bi on
the unique path from bs to bt in the backbone T also contain v. The width of a decomposition is
defined as the maximum bag size minus one. The tree-width of a graph is the minimum width
over all decompositions. For simplicity, we will further assume in our overview that all treedecompositions are well behaved, i.e., the subgraph of G induced by a bag is connected and no
7

bag is a subset of another bag. Given a tree-decomposition that does not have these properties
it is possible to obtain one that does by removing superfluous bags and splitting disconnected
bags.
Chordal Graphs and Perfect Elimination Orders An undirected graph G is chordal, if in
every cycle C of at least four nodes there is a chord, i.e., a pair of nodes that are adjacent in the
graph G but not adjacent in the cycle C. A node is call simplicial if its neighbors form a clique.
Every chordal graph contains at least one simplicial node [23]. A perfect elimination order of
an undirected graph G is a node order v1 , v2 . . . vn , such that vi is simplicial in the subgraph
of G induced by vi , vi+1 . . . vn . Not every graph possesses a perfect elimination order. Chordal
graphs can be characterized as the graphs that possess a perfect elimination order [23]. Such an
order can be constructed, given a chordal graph, by iteratively removing simplicial nodes from a
chordal graph. As chordal graphs can have several simplicial nodes, chordal graphs can possess
several perfect elimination orders.
The CCH contraction order is a perfect elimination order of the supergraph G0 constructed
in the CCH. G0 is thus a chordal supergraph of the input graph G. In the context of chordal
graphs, a contraction order is also called elimination order.
Converting Structures A tree-decomposition can be constructed, given a chordal supergraph
G0 of a graph G as follows: Start by identifying the maximal cliques in G0 . This can be done
in polynomial running time using the perfect elimination ordering vi . Every maximal clique of
G0 must appear as union of a node vi with its neighborhood in the subgraph of G0 induced by
vi , vi+1 . . . vn . Testing which of these linearly many neighborhoods are maximal cliques results in
all maximal cliques being found. The maximal cliques of G0 are the bags of the decomposition.
We denote their set by B. These cliques are the nodes of the tree-backbone T . It remains to
construct the edges of the tree-backbone T . We therefore consider the weighted undirected graph
T 0 = (B, E), where an edge {x, y} exists if the intersection of bags x and y is non-empty. An edge
{x, y} is weighted by the number of nodes in the intersection of x and y. T 0 is not necessarily
a tree and thus not a valid backbone. However, every maximum spanning tree of T 0 is a valid
tree-backbone [6]. Computing a maximum spanning tree thus completes the tree-decomposition
construction. Given a tree-decomposition we can easily get back to the corresponding chordal
graph. The transformation consists of adding edges between all nodes in each bag.
This gives us three views that encode essentially the same information: Chordal supergraphs,
tree-decompositons, and elimination orders. These are interconvertible as follows:
• Given an undirected graph G and an elimination order o we can get to a chordal supergraph
G0 by iteratively contracting the nodes.
• By computing a perfect elimination order of G0 we can obtain an elimination order o0 of
G. The orders o and o0 are not necessarily the same, but they induce the same chordal
supergraph.
• From the chordal supergraph G0 we can construct a tree-decomposition of G as described
above.
• From the tree-decomposition of G we can get back to the chordal supergraph G0 by adding
edges in each bag.
It is guaranteed that none of these transformations increases the width of the corresponding
tree-decomposition.

8

Elimination Tree With respect to an elimination order we can define the elimination tree 2 .
For every node vi at position i in the order, we define its parent in the elimination tree as the
first node vj that appears in the order after vi such that an edge {vi , vj } exists. If no such vj
exists, the node is a root in the elimination tree.
It can be shown that the nodes in the search space of v is the set of ancestors of v in the
elimination tree [5]. In a shortest path distance query from s to t in a CCH, the ancestors of s
and t in the elimination tree are therefore the set of nodes touched by the CCH query algorithm.
It is therefore our goal to minimize the depth of the elimination tree.
Two elimination orders that yield the same chordal supergraph do not necessarily yield the
same elimination tree. The minimum depth over the elimination trees over all elimination orders
is called the tree-depth.
Computing Elimination Orders Commonly used algorithms to compute tree-decompositions
of large graphs in practice are heuristics that try to guess the elimination order. The simplest is
the minimum degree heuristic [37, 26]. It consists of iteratively contracting a node of minimum
degree. This simple algorithm is usually fast and works well enough on some graphs but at least
on road graphs there is a large gap to the optimal orders [19].
A more sophisticated approach is called nested dissection [25, 36]. The idea is precisely the
same as the approach we used to compute the CCH contraction orders. It consists of finding
a small balanced separator and placing these nodes at the end of the elimination order. The
separator is then removed from the graph and the algorithm recursively continues on both sides.
The operation of contracting a separator last can be interpreted as trying to guess a central
edge in the tree-backbone. Denote by a and b two non-leaf bags and by {a, b} an edge in the
backbone. The nodes of a ∩ b form a separator of the input graph [7]. If the edge {a, b} is
positioned near the center of the tree-backbone then the sides of the separator a ∩ b are likely
of roughly the same size. This motivates why nested dissection works in practice.

3.5

Bounding CCH Performance in Terms of Tree-Width and -Depth

We can express the CCH performance in terms of tree-depth, which can be bounded using the
tree-width.
A tree-decomposition of minimum width does not necessarily have an elimination order that
results in a minimum elimination tree depth. For example, a path has a tree-decomposition
of width 1 as it is a tree. However, no elimination order exists that yields a depth smaller
than n/2. Fortunately, a tree-decomposition exists with a width in O(log n) and a depth in
O(log n). It can be obtained using nested dissection with balanced separators. Besides small
bags, a tree-decomposition must also have a logarithmic diameter to allow for a low elimination
tree depth. This logarithmic diameter corresponds to the logarithmic recursion depth obtained
by recursively bisecting a graph along a balanced separator.
Denote by tw the tree-width of the input graph G and by td its tree-depth. [10] have
shown that there always exists an elimination order of G that yields an elimination tree depth
of O(tw log n) but the corresponding tree-decomposition does not necessarily have a minimum
width. Fortunately, the depth of every elimination tree is an upper bound to the width of the
corresponding tree-decomposition. There is therefore always a tree-decomposition with width
O(tw log n) that admits an elimination tree of depth O(tw log n). Assuming that we could
construct an elimination order Π of minimum elimination tree depth, which is NP-hard [38], we
could bound the performance of the corresponding CCH in terms of td.
A CCH-query from s to t explores the search spaces of s and t. The number of nodes in each
of them is bounded by td and thus no more than 2td nodes are visited. The running time of
this exploration is however only bounded by O(td2 ) as the subgraphs can be dense. In practice
2

The elimination tree is actually a forest, if the input graph is disconnected.

9

(a) Balanced cut C

(b) Unbalanced cut C

(d) Source side cut C 0

(c) Extra sources to avoid C

(e) Target side cut C 0

Figure 1: An ellipse represents a graph and the curved lines are cuts. The “+”-signs represent
source nodes and “×”-signs represent target nodes.
the average depth and the average number of arcs over all nodes might be a better performance
indicator than the maximum numbers. Fortunately, using a simple algorithm that proceeds topdown along the elimination tree we can compute the average and maximum number of nodes
and arcs in the subgraph of each node efficiently.
We are further interested in the number of edges and triangles in G0 as these correspond
to the customization running times and the memory consumption, respectively. The number of
P
edges is equal to v do (v) when directing every edge of G0 upward. The number of triangles in
which a node v appears as lowest node is (do (v) · (do (v) − 1))/2 as the upper neighbors of v form
P
a clique. The total number of triangles is therefore v (do (v) · (do (v) − 1))/2.
We can bound do (v) using the width of the tree-decomposition corresponding to Π. Recall
that this decomposition does not necessarily have a minimum width, but, as shown by [10], its
width can be bounded by td. We thus obtain the bounds of O(ntd) for the number of edges
and O(ntd2 ) for the number of triangles. Fortunately, for planar graphs [36, 27] have shown
that, there exist nested dissection orders such that, the number of edges in G0 is bounded by
O(n log n). This is usually smaller than O(ntd) upper edge count bound. Further, this formula
can also be used to bound the number of triangle by O(ntd log n) as follows: We can bound
P 2
P
P
v do (v) by (maxv do (v)) ·
v do (v). maxv do (v) is at most td and
v do (v) is the number
of edges, i.e., at most O(n log n). Unfortunately, [36, 27] do not analyze the corresponding
elimination tree heights. It is thus unknown whether they are in O(td). Road graphs are not
strictly planar, but often planar enough to make this result relevant.

4

Core FlowCutter Algorithm

In the previous two sections, we described how finding good graphs cuts and separators is
beneficial to many applications. In this section, we propose our novel algorithm to compute
graph cuts named FlowCutter.
FlowCutter works by computing a sequence of st-cuts of increasing size. The more imbalanced cuts are computed first and are followed by more balanced ones. The cuts in this sequence
form, after removing dominated ones, the heuristically approached Pareto-set. During its execution our algorithm maintains a maximum flow. With respect to this flow there is a source-side
cut CS and a target-side cut CT . Our algorithm picks one of the two as the next cut C that it
inserts into the set. After choosing C it modifies the set of source and target nodes and potentially augments the maintained flow. This results in a new pair of source-side and target-side
cuts. FlowCutter picks CS as C if there are less or equally many nodes on the source side of CS
10

than there are on the target side of CT .
Consider the situation depicted in Figure 1. Initially s is the only source node and t is the
only target node. Our algorithm starts by computing a maximum st-flow. If we are lucky and
the cut C is perfectly balanced as in Figure 1a then our algorithm is finished. However, most
of the time we are unlucky and we either have the situation depicted in Figure 1b where the
source’s side of C is too small or the analogous situation where the target’s side of C is too
small. Assume without loss of generality that the source’s side is too small. Our algorithm now
transforms non-source nodes into additional source nodes to invalidate C and computes a new
more balanced st-min-cut C 0 , the second cut in the sequence. To invalidate C, our algorithm
does two things: It marks all nodes on the source’s side of C as source nodes and marks one
node as source node on the target’s side of C that is incident to a cut edge. This node on the
target’s side is called the piercing node and the corresponding cut arc is called piercing arc. The
situation is illustrated in Figure 1c. All nodes on the source’s side are marked as source node to
assure that C 0 does not cut through the source’s side. The piercing node is necessary to assure
that C 0 6= C. Choosing a good piercing arc is crucial for good quality. In this section, we assume
that we have a piercing oracle that determines the piercing arc given C in time linear in the
size of C. In Section 4.2 we describe heuristics to implement such a piercing oracle. For the
algorithm to make progress we need that C 0 is non-dominated. As its size is at least the size of
C, this is equivalent with C 0 being more balanced than C. However, we can only guarantee this
if C 0 is, just as C, a source-side cut as in Figure 1d. If C 0 is a target-side cut as in Figure 1e
then C 0 might have a worse balance than C. Luckily, as our algorithm progresses, either the
target side will catch up with the balance of the source side or another source side cut is found.
In both cases our algorithm eventually finds a cut with a better balance than C.
Our algorithms grows the sides around the source and target nodes. By doing so it can
guarantee that both sides are connected. In some applications, this is a desired property. In
others, it might be an obstacle to finding the smallest possible cuts. Depending on the application
this property is therefore either a feature or a drawback of our algorithm.
Our algorithm computes the st-min-cuts by finding max-flows and using the max-flow-mincut duality [21]. It assigns unit capacities to every edge and computes the flow by successively
searching for augmenting paths. A core observation of our algorithm is that turning nodes into
sources or targets never invalidates the flow. It is only possible that new augmenting paths are
created increasing the maximum flow intensity. Given a set of nodes X we say that forward
growing X consists of adding all nodes y to X for which a node x ∈ X and a non-saturated
xy-path exist. Analogously, backward growing X consists of adding all nodes y for which a
non-saturated yx-path exists. The growing operations are implemented using a graph traversal
algorithm (such as a DFS or BFS) that only follows non-saturated arcs. The algorithm maintains
besides the flow values four node sets: the set of sources S, the set of targets T , the set sourcereachable nodes SR , and the set of target-reachable nodes TR . An augmenting path exists if and
only if SR ∩ TR 6= ∅. Initially, we set S = {s} and T = {t}. Our algorithm works in rounds.
In every round it tests whether an augmenting path exists. If one exists, the flow is augmented
and SR and TR are recomputed. If no augmenting path exists, then it must enlarge either S or
T . This operation also yields the next cut. It then selects a piercing arc and grows SR and TR
accordingly. The pseudo-code is presented as Algorithm 1.

4.1

Running Time.

Assuming a piercing oracle with a running time linear in the current cut size, we can show
that the algorithm has a running time in O(cm) where c is the size of the most balanced cut
found and m is the number of edges in the graph. The exact details are slightly more involved
but, fortunately, the core argument is simple. All sets only grow unless we find an augmenting
path. As each node can only be added once to each set, the running time between finding two
augmenting paths is linear. In total, we find c augmenting paths. The total running time is
11

Algorithm 1: Pseudo-Code illustrating the core st-bisection algorithm.
1
2
3
4
5
6
7
8
9
10
11

12
13
14
15
16

17
18
19

S ← {s}; T ← {t};
SR ← S; TR ← T ;
forward-grow SR ; backward-grow TR ;
while S ∩ T = ∅ do
if SR ∩ TR 6= ∅ then
augment flow by one;
SR ← S; TR ← T ;
forward-grow SR ; backward-grow TR ;
else
if |SR | ≤ |TR | then
forward-grow S;
// now S = SR
output source side cut edges;
x ← pierce node;
S ← S ∪ {x}; SR ← SR ∪ {x};
forward-grow SR ;
else
// Analogous for target side
end
end
end

thus in O(cm). The remainder of this section contains the details necessary to formally show
the O(cm) worst case running time.
The lines 1-3 of Algorithm 1, which initialize the data structures, have a running time in
O(m) and are therefore unproblematic. The condition in line 4 can be implemented in O(1) as
follows: S and T only grow. Using two bit-arrays with n elements we can store which node is
in S and which in T . When adding a node, we raise the corresponding bit and check whether
the bit in the array is set. As S and T only grow, the loop will abort the next time line 4 is
reached, once there is one node for which both bits are set.
We can use a similar structure for the test between SR and TR in line 5. SR and TR only
grow as long as the true-branch in lines 6-8 is not executed. Outside of the true-branch we can
therefore use the same bit-vector trick to achieve an O(1)-test in line 5. The lines 6-8 consist
of the code that augments the flow, i.e., they have a running time of O(m) each time that the
branch is executed. In O(m) running time we can reset the bit-arrays, i.e., entering the truebranch is unproblematic for the running time of the test in line 5. We can therefore account for
the running time needed to manage the bit-arrays in the lines 6-8 and have an O(1)-test in line
5.
As already stated, the lines 6-8 augment the flow and need O(m) running time each time
that they are executed. Fortunately, there can be at most c path augmentations. The total time
spent in the lines 6-8 over the algorithm’s execution is therefore in O(cm).
In addition to maintaining the bit-arrays for SR and TR , we can keep track of the number
of elements in the sets. This allows us to implement the test in line 10 in O(1).
Showing that the algorithm spends no more than O(cm) running time in the lines 11-15 and
in the analogous lines 16-17 is the tricky part of the algorithm’s analysis. The lines 16-17 follow
directly by symmetry and therefore we focus on the lines 11-15.
We will first establish that the lines 10-17 are only executed at most m times. In each
iteration an arc is chosen as piercing arc. After being chosen, an arc cannot participate in
another cut and can therefore not be chosen a second time as piercing arc. As there are only m
12

arcs, the number of iterations is bounded by m.
For each of S, T , SR , and TR we maintain the data structures of a breadth-first search3 , i.e.,
a queue and a bit-array of n elements. Growing a set as seen in the lines 11 and 15 consists of
removing nodes from the corresponding queue and visiting neighboring nodes until the queue is
emptied, i.e., executing the regular breadth-first search algorithm. Adding a node to the set as
seen in line 14 consists of adding the node to queue and raising the corresponding in the bitarray. It is thus clear the operation in line 14 is in O(1) and as there are at most m iterations,
the total time spent in line 14 is in O(m) which is below the claimed running time of O(cm).
The growing of the sets S and T is also in O(m) as we never remove an element from S nor
T and they therefore consist of standard breadth-first searches. These searches are interrupted
from time to time but this does not change the fact that the total running time spent in them
is in O(m). Analyzing the running time required to grow the sets SR and TR is more difficult
as the states of the associated searches can be reset in line 7. Fortunately, as we have already
established, line 7 can only be executed at most c times. There are therefore only O(c) state
resets. Between two resets the search consists of a normal breadth-first-search with a running
time in O(m). The total running time is therefore bounded by O(cm).
We assumed that the piercing oracle requires a running time proportional to the number of
arcs in the cut from which it must chose. The number of cut arcs never decreases. Further,
there are c cut arcs at the end. We therefore know that c is an upper bound to the size of every
intermediate cut. Further, as there are at most m iterations, we have bounded the total running
time in line 13 by O(cm).
It remains to show that line 12, which outputs the cuts, does not require more than O(cm)
running time. This seems trivial at first but the details are significantly more involved than
one would naively expect. Following the argumentation for line 13, we know that the operation
must run in O(c) running time to achieve a total running time of O(cm). The algorithm must
therefore output the cuts as list of cut arcs and not as bit-array that maps each node to a side,
as is often done in competitor algorithms. Outputting bit-arrays would be too slow. Another
problem consists of identifying the cut-arcs efficiently. In O(c) running time, the algorithm
cannot iterate over all nodes in S or T to determine all outgoing arcs, which is needed to find
the cut-arcs in the straight-forward way. The trick to achieve the required running time consists
of maintaining two lists of saturated arcs. The first list consists of saturated arcs that depart in
S and could be part of the cut. The second list consists of saturated arcs that enter T and works
analogously. If the algorithm encounters a saturated arc when growing S in line 11, it adds the
arc to the list of S. It does this regardless of whether the arc is a cut arc. When reaching line
12, this list contains all cut arcs but also possibly additional saturated arcs that are not part
of the cut. The algorithm therefore iterates over all arcs before outputting them and removes
those that are no cut arcs. This step can have a running time larger than O(c). Fortunately, as
every arc can only be added once to the list, it can also only be removed once. The total running
time needed for the removal is therefore in O(m) and we do not need to account for it in line
12. Further, after removing superfluous arcs at most O(c) remain, which is within the required
bounds. This concludes the proof that the running time of our core algorithm is within O(cm).

4.2

Piercing Heuristic

In this section, we describe how we implement the piercing oracle used in the previous section.
Given an unbalanced arc cut C, the piercing oracle should select a piercing arc that is not part
of the final balanced cut in at most O(|C|) time. Piercing the source side and target side cuts are
analogous and we therefore only describe the procedure for the source side. Denote by a = (q, p)
the piercing arc with piercing node p 6∈ S.
Our piercing heuristic is composed of two parts: The primary and the secondary heuristic.
3

A depth-first search would work too.

13

a
s

b
c

Figure 2: The curves represent cuts, the current one is solid. The arrows are cut-arcs, bold ones
result in augmenting paths. The dashed cut is the next cut where piercing any arc results in an
augmenting path.
The primary heuristic first narrows down the set of potential piercing arcs and the secondary
heuristic then chooses from this smaller set.

4.3

Primary Heuristic: Avoid Augmenting Paths

The first heuristic consists of avoiding augmenting paths whenever possible. Piercing an arc
a leads to an augmenting path, if and only if p ∈ TR , i.e., a non-saturated path from p to
a target node exists. As our algorithm has computed TR , it can determine in constant time
whether piercing an arc would increase the size of the next cut. The proposed heuristic consists
of preferring edges with p 6∈ TR if possible. It is possible that none or multiple p 6∈ TR exist. In
this case our algorithm employs a further heuristic to choose the piercing arc among them.
However, the secondary heuristic is often only relevant in the case that an augmenting path
in unavoidable. Consider the situation depicted in Figure 2. Our algorithm can choose between
three piercing arcs a, b, and c. It will not pick a as this would increase the cut size. The question
that remains is whether b or c is better. The answer is that it nearly never matters. Piercing
b or c does not modify the flow and therefore not TR . Which piercing arcs result in larger cuts
is therefore left unchanged. No matter whether b or c is picked, picking a in the next iteration
results again in an augmenting path. The algorithm will therefore eventually end up with the
same cut composed solely of arcs that should be avoided unless perfect balance is achieved first.
This cut is represented as dashed line in Figure 2. We know that the dashed cut has the same
size as all cuts found between the current cut and the dashed cut. Further, the dashed cut has
the best balance among them and therefore dominates all of them. It therefore does not matter
which of these dominated cuts are enumerated and in which order they are found.
This means that most of the time our avoid-augmenting-paths heuristic does the right thing.
However, it is less effective when cuts approach perfect balance. In this case it is possible that
perfect balance is achieved before the dashed cut is found. The result consists of a race between
source and target sides to claim the last nodes. Not the best side wins, but the first that gets
there.

4.4

Secondary Heuristic: Distance-Based

If our primary avoid-augmenting-paths heuristic does not uniquely determine the piercing arc,
we use a secondary distance heuristic to tie-break between the remaining choices. Our algorithm
picks a piercing arc such that dist(p, t) − dist(s, p) is maximized, where s and t are the original
source and target nodes. The dist(p, t)-term avoids that the source side cut and the target side
cut meet as nodes close to t are more likely to be close to the target side cut. Subtracting
dist(s, p) is motivated by the observation that s has a high likelihood of being positioned far
away from the balanced cuts. A piercing node close to s is therefore likely on the same side as s.
Our algorithm precomputes the distances from s and t to all nodes before the core algorithm is
run. This allows it to evaluate dist(p, t) − dist(s, p) in constant time inside the piercing oracle.

14

1.5

c=0.7

cut

s

t

●

●

−1.5

−0.5

0.5

c=1.3

−1.5 −1.0 −0.5

0.0

0.5

1.0

Figure 3: Geometric interpretation of the distance heuristic.
The distance heuristic has a geometric interpretation as depicted in Figure 3. We interpret
the nodes as positions in the plane and the distances as being euclidean. The set of points p
for which kp − tk2 − kp − sk2 = c holds for some constant c is one branch of a hyperbola whose
two foci are s and t. The figure depicts the branches for c = 1.3 and c = 0.7. The heuristic
prefers piecing nodes on the c = 1.3-branch as it maximizes c. A consequence of this is that the
heuristic works well if the desired cut follows roughly a line perpendicular to the line through s
and t. This heuristic works on many graphs but there are instances where it breaks down. For
example cuts with a circle-like shape are problematic. This geometric interpretation also works
in higher-dimensional spaces.

5

Extensions

Our base algorithm can be extended to compute general small cuts that are independent of an
input st-pair, to compute node separators, and to compute contraction orders.

5.1

General Cuts

Our core algorithm computes balanced st-cuts. In many situations cuts independent of a specific st-pair are needed. This problem variant can be solved with high probability by running
FlowCutter q times with st-pairs picked uniformly at random. Indeed, suppose that C is a
Pareto-optimal cut such that the larger side has α · n nodes (i.e. α = ( + 1)/2) and q is the
number of st-pairs. The probability that C separates a random st-pair is 2α(1 − α). The success
probability over all q st-pairs is thus 1 − (1 − 2α(1 − α))q . For  = 33% and q = 20, the number
of pairs we recommend in our experiments, the success probability is larger than 99.99%. For
larger α this rate decreases. However, it is still large enough for all practical purposes, as for
α = 0.9 (i.e.  = 80%) and q = 20 the rate is still slightly above 98.11%. The number of st-pairs
needed does not depend on the size of the graph nor on the cut size. If the instances are run one
after another then the running time depends on the worst cut’s size which may be more than
c. We therefore run the instances simultaneously and stop once one instance has found a cut of
size c. The running time is thus in O(qcm). As we set q to a constant value of at most 100 in
our experiments, the running time is in O(cm).
This argumentation relies on the assumption that it is enough to find an st-pair that is
separated. However, in practice the positions of s and t in their respective sides influence the
performance of our piercing heuristic. As a result it is possible that in practice more st-pairs
are needed than predicted by the argument above because of effects induced by the properties
of the piercing oracle.

15

a

ai

b
c

ao

d

co

ci
f

e

ei

bi
do

di
fi

eo

(a) Input graph

bo

fo

(b) Expanded graph

Figure 4: Expansion of an undirected graph G into a directed graph G0 . The dotted arrows are
internal arcs. The solid arrows are external arcs.

Epsilon [%]

100

●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●

75
50

●
●
●
●
●
●
●

25
●
●
●●
●
●
●
●
●
●
●
●●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●

0
0

50

100

150

200

250

Cut Size

Figure 5: Edges cuts found by FlowCutter with 20 random source-target pairs for the Central
Europe graph used in the experiments.

5.2

Node Separators

To compute contraction orders, node separators are needed and not edge cuts. To achieve
this, we employ a standard construction to model node capacities in flow problems [22, 1]. We
transform the symmetric input graph G = (V, A) into a directed expanded graph G0 = (V 0 , A0 )
and compute flows on G0 . We expand G into G0 as follows: For each node x ∈ V there are two
nodes xi and xo in V 0 . We refer to xi as the in-node and to xo as the out-node of x. There is
an internal arc (xi , xo ) ∈ A0 for every node x ∈ V . We further add for every arc (x, y) ∈ A an
external arc (xo , yi ) to A0 . The construction is illustrated in Figure 4. For a source-target pair s
and t in G we run the core algorithm with source node so and target node ti in G0 . The algorithm
computes a sequence of cuts in G0 . Each of the cut arcs in G0 corresponds to a separator node
or a cut edge in G depending on whether the arc in G0 is internal or external. From this mixed
cut our algorithm derives a node separator by choosing for every cut edge in G the endpoint on
the larger side. Unfortunately, using this construction, it is possible that the graph is separated
into more than two components, i.e., we can no longer guarantee that both sides are connected.

5.3

Contraction Orders

Our algorithm constructs contraction orders using an approach based on nested dissection [25,
36]. It bisects G along a node separator Q into subgraphs G1 and G2 . It recursively computes
orders for G1 and G2 . The order of G is the order of G1 followed by the order of G2 followed by
the nodes in Q in an arbitrary order. Selecting Q is unfortunately highly non-trivial.
The cuts produced by FlowCutter can be represented using a plot such as in Figure 5.
Each point represents a non-dominated cut. The question is which of the many points to
choose. After some experimentation, we went with the following heuristic: Pick a separator with
minimum expansion and at most 60% imbalance. This choice is not perfect as the experiments
of Section 6.4 show but works well in most cases. Picking a cut of minimum expansion given

16

a Pareto-cut-set is easy. However, we know of no easy way to do this using an algorithm that
computes a single small cut of bounded imbalance, as all the competitor algorithms do. It is
therefore not easy to swap FlowCutter out for any of the competitors without also dropping
expansion as optimization criterion.
We continue the recursion until we obtain trees and cliques. On cliques any order is optimal.
On trees an order can be derived from a so called optimal node ranking as introduced in [33]. A
node ranking of a tree is a labeling of the nodes with integers 1, 2 . . . k such that on the unique
path between two nodes x and y with the same label there exists a node z with a larger label.
An optimal node ranking is one with minimum k. Contracting the nodes by increasing label
yields an elimination tree of minimum depth. In [41] it has been shown that these ranking can
be computed in linear running time.
Special Preprocessing for Road Graphs Road graphs have many nodes of degree 1 or 2.
We exploit this in a fast preprocessing step similar to [18] to significantly reduce the graph size.
Our algorithm first determines the largest biconnected component B using [31] in linear time.
It then removes all edges from G that leave B. It continues independently on every connected
component of G as described in the next paragraph. The set of connected components usually
consists of B and many tiny often tree-like graphs. The resulting orders are concatenated such
that the order of B is at the end. The other orders can be concatenated arbitrarily.
For each connected component our algorithm starts by marking the nodes with a degree
of 3 or higher. For each degree-2-chain x, y1 . . . yk , z between two marked nodes x and z with
x 6= z, it adds an edge {x, z}. It then splits the graph into the graph G≥3 induced by the
marked nodes and the graph G≤2 induced by the unmarked nodes. Edges between marked and
unmarked nodes are dropped. G≤2 consists of the disjoint union of paths. As paths are trees,
we can therefore employ the node-ranking-based tree-ordering algorithm described above to
determine a node order. For G≥3 we determine an order using FlowCutter and nested dissection
as described above We position the nodes of G≤2 before those of G≥3 and obtain the node order
of the connected component.

6

Experiments

We compare Flowcutter to the state-of-the-art partitioners KaHip [39], Metis [34], and InertialFlow [42]. There is a superficial comparison with PUNCH [16] in Section 6.3. We present
three experiments: (1) we compare the produced contraction orders in terms of CCH performance in Section 6.2 on road graphs made available during the DIMACS challenge on shortest
paths [17], (2) compare the Pareto-cut-sets in more detail in Section 6.3 on the same road
graphs, and (3) evaluate FlowCutter on non-road graphs using the Walshaw benchmark set [44]
in Section 6.5. Section 6.1 describes the experimental setup common to all experiments. All
experiments were run on a Xeon E5-1630 v3 @ 3.70GHz with 128GB DDR4-2133 RAM.

6.1

Algorithm Implementations Used and Their Configurations

Edge Cut Algorithm We use FlowCutter in three variants denoted by F3, F20, and F100,
with 3, 20, and 100 random source-target-pairs respectively. InertialFlow was introduced in [42]
but no code was published. Fortunately, the idea is simple and we therefore were able to
reimplement the algorithm. We refer to it using the letter I. Metis is a well-known general
graph partitioner based on a multi-level scheme. The original authors published source code,
which we used in our experiments. We compare against Metis 5.1.0 which is the newest version
at the time of writing and refer to it as M. KaHip also uses a multi-level scheme but adds a
lot of optimizations compared to Metis that can drastically decrease the cut sizes. The KaHip
source code is also available and thus we use it for our experiments. At the time of writing, the

17

current version of KaHip is 1.00. Unfortunately, we have observed several regressions compared
to earlier versions. These regressions are due to a bug being fixed that caused certain expensive
flow-based refinement steps not being run for higher imbalances. The newer version achieves
smaller cuts at the expense of higher running times for higher imbalances. Because of these
regressions and for comparability with previous works, we also include comparisons with the
earlier versions KaHip 0.61 and KaHip 0.73 which were the current versions and therefore used
when we performed the experiments for [19] and [29] respectively. We use KaHip in the strong
preconfiguration and add --enforce_balance to the commandline for max  = 0. We refer to
the three variants as K0.61, K0.73, and K1.00.
Node Ordering Algorithms Metis provides its own node ordering tool called ndmetis, which
we use. Unfortunately, no other package provides a similar tool. We have therefore implemented
a nested dissection algorithm on top of them. For KaHip 1.00 and InertialFlow we use the same
straight-forward nested dissection implementation that computes one edge cut at each level and
recurses until either cliques or trees are reached. Edge cuts are transformed into node separators
by picking the nodes on one side incident to the cut edges. For KaHip we use a maximum
imbalance of 20% and for InertialFlow we use 60%. For KaHip 0.61 we use an older nested
dissection implementation originally written for [19]. It is not optimized for running time and
only for quality. At each level, it invokes KaHip several times with different random seeds and
picks the smallest cut found. It calls KaHip repeatedly on every level until for ten consecutive
calls no smaller cut is found. We do this to reliably get rid of variations in achieved cut sizes
that are due to randomization. However, this setup is unfavorable to KaHip as it results in large
running times. We decided to stick with the old ordering routine for K0.61 for comparability
with [19] and use an ordering scheme for K1.0 that only computes one cut per level. The
FlowCutter nested dissection implementation is based on the same code as used for KaHip 1.00
and InertialFlow but uses the separator variant of FlowCutter and performs the low-degree node
optimizations described in Section 5.3.
KaHip v1.00 includes a more sophisticated tool to transform edge cuts into node separators
using the algorithm of [40]. We tried using it in combination with the newer nested dissection
scheme with one separator per level, but we needed 19 hours to compute orders for the small
California and Nevada graph used in our experiments. We were not able to compute orders on
the larger instances in reasonable time and therefore omit this algorithm from our comparison.

6.2

Order Experiments

We computed contraction orders for 4 DIMACS roads graphs [17]. Our results are summarized
in Table 1.
Instances The smallest test instance is the DIMACS Colorado graph with n = 436K and
m = 1M. Next is California and Nevada with n = 1.9M and m = 4.6M, followed by (Western)
Europe with n = 18M and m = 44M and finally a graph encompassing the whole USA with
n = 24M and m = 57M.
Relations between Columns Table 1 contains a lot of data. However, some columns are
related. We therefore first point these relations out and then limit our discussion to the remaining
non-related columns. We observe that, modulo small cache effects, the customization time is
correlated with the number of triangles and the average query running time is correlated with
the number of arcs in the CCH. These correlations are non-surprising and were predicted by
CCH theory. Denote by ns and ms the number of nodes and arcs in the search space. For the
average numbers we observe that 1.7 ≤ ns (n2s −1) /ms ≤ 2.6 and for the maximum numbers we
observe that 2.1 ≤ ns (n2s −1) /ms ≤ 3.9, which indicates that the search spaces are nearly complete
18

Search Space
Nodes

Up.

Running times

in CCH

#Tri. Tw.

[·106 ]

[·106 ] Bd.

[s]

[ms]

[µs]

6.4 102
7.2 103
6.9 99
7.4 119
4.8 91
4.4 87
4.4 87

2.0
3 837.1
1 052.4
7.4
10.3
61.0
285.9

18
21
20
21
15
14
14

26
20
20
24
18
17
18

9.9
18 659.3
6 023.6
42.6
64.1
386.8
1 831.8

88
89
86
84
69
68
65

60
30
30
31
27
26
26

Col

M
155.6
K0.61 135.1
K1.00 136.4
I
151.2
F3
126.3
F20 122.4
F100 122.5

354
357
357
542
280
262
264

6.1
4.6
4.8
6.2
4.1
3.8
3.8

22
22
22
38
15
14
14

1.4
1.7
1.5
1.5
1.3
1.3
1.3

Cal

Order Cust. Query

M
275.5
K0.61 187.7
K1.00 184.9
I
191.4
F3
177.5
F20
170.0
F100 169.5

543
483
471
605
356
380
380

17.3
7.0
6.8
7.1
6.2
5.6
5.6

53
37
38
53
24
26
26

6.5
7.5
7.0
6.9
5.9
5.8
5.8

Eur

Avg. Max.

#Arcs

M 1 223.4 1 983 441.4
K0.61 638.6 1 224 114.3
K1.00 652.5 1 279 113.4
I
732.9 1 569 149.7
F3
734.1 1 159 140.2
F20 616.0 1 102 102.8
F100 622.6 1 105 104.8

933
284
287
414
312
268
239

69.9 1 390.4 926
125.9 2 241
73.9 578.2 482 213 091.1 971
68.3 574.5 451 242 680.5 934
67.4 589.7 516
1 017.2 935
60.3 519.4 531
2 531.6 853
58.8 459.6 455 16 841.5 784
58.8 459.4 449 85 312.8 766

1 164
303
297
385
365
270
278

USA

Avg. Max.

Arcs

[·103 ]

M
990.9
K0.61 575.5
K1.00 540.3
I
533.6
F3
562.7
F20 490.6
F100 490.9

633
185
208
291
159
154
154

86.0 1 241.1 676
170.8 2 111
97.9 737.1 366 265 567.3 1 250
88.7 648.3 439 315 942.6 1 097
88.8 682.0 384
1 076.8 1 125
75.9 478.4 321
2 108.7 858
74.3 440.5 312 12 379.2 812
74.3 442.6 311 59 744.6 886

651
202
179
177
191
156
155

1 685 249.1
1 041 71.3
1 063 62.3
1 371 62.0
906 66.4
868 52.7
863 52.8

36.4
34.2
33.4
34.1
23.4
21.8
21.8

180
160
143
161
127
132
132

Table 1: Contraction Order Experiments. We report the average and maximum over all nodes v
of the number of nodes and arcs in the CCH-search space of v, the number of arcs and triangles in
the CCH, and the induced upper treewidth bound. We additionally report the order computation
times, the customization times, and the average shortest path distance query times. Only the
customization times are parallelized using four cores. The customization times are the median
over nine runs to eliminate variance. The query running times are averaged over 106 st-queries
with s and t picked uniformly at random. Several CCH customization variants exist. The times
reported are for a non-amortized, non-perfect customization, with SSE and uses precomputed
triangles.

19

graphs. The number of nodes and the number of arcs are thus related. We can therefore say
that search space is small or large without indicating whether we refer to nodes or arcs as one
implies the other.
Search spaces One of the FlowCutter variants always produces the smallest search spaces.
KaHip produces the next smaller search spaces, followed by InertialFlow. Metis is last by a large
margin. It is interesting that the USA graph has a smaller search space than the Europe graph.
The ratio between the average and the maximum search space sizes is very interesting. A high
ratio indicates that a partitioner often finds good cuts, but at least one cut is comparatively
bad. This ratio is never close to 1, indicating that road graphs are not perfectly homogeneous.
In some regions, probably cities, the cuts are worse than in some other regions, probably the
country-side. However, compared to the competitors, the ratio is higher for InertialFlow. This
illustrates that its geography-based heuristic is effective most of the time but in few cases fails
noticeably at finding a good cut.
Number of Arcs A small search space size is not equivalent with the CCH containing only few
arcs. It is possible that vertices are shared between many search spaces and thus the CCH can
be significantly smaller than the sum of the search space sizes. This effect occurs and explains
why the number of arcs in CCH is orders of magnitude smaller than the sum over the arcs in all
search spaces. Further, minimizing the number of arcs in the CCH is not necessarily the same as
minimizing the search space sizes. This explains why Metis beats KaHip in terms of CCH size
but not in terms of search space size. InertialFlow seems to be comparable to Metis in terms of
CCH size, as their CCH arc counts are never significantly different. However, FlowCutter beats
all competitors and clearly achieves the smallest CCH sizes.
Number of Triangles A third important order quality metric is the number of triangles
in the CCH. Metis is competitive on the two smaller graphs, but is clearly dominated on the
continental sized graphs. InertialFlow and KaHip seem to be very similar on all but the USA
graph. On the USA graph K1.0 is ahead of both InertialFlow and K0.61. FlowCutter also wins
with respect to this quality metric producing between 20% and 30% fewer triangles than the
closest competitor.
Treewidth As the CCH is essentially a chordal graph which are closely tied to tree-decompositions,
we can easily obtain upper bounds on the tree-width of the input graphs as a side product. This
quality metric is not directly related to CCH performance, but is of course indirectly related as
most of the other criteria can be bounded in terms of it. As such it reflects the same trend:
Metis is worst, followed by InertialFlow, followed by KaHip, and FlowCutter with the best
bounds. Analogous to the search space sizes, we observe that the USA graph has a significantly
lower tree-width than the Europe graph, assuming that our upper treewidth bounds are not
completely off.
Running Time Quality comes at a price and thus the computation times of the orders follow
nearly the opposite trend: KaHip is the slowest, followed by FlowCutter, followed by InertialFlow, while Metis is astonishingly fast.
K1.00 vs K0.61 The two KaHip versions seem to be very similar. Sometimes the newer
version K1.00 is ahead and sometimes the older version K0.61 wins in terms of order quality.
We explain this effect by differences in implementation in our nested dissection code. Recall that
K0.61 takes the best cut of at least 10 iterations on each level, whereas K1.00 only computes
a single cut. This means that K1.00 is more sensible to random fluctuations coming from bad
random seeds than K0.61. On average, one run of K1.00 is better than one run of K0.61.
20

max 

F3

0
1
3
5
10
20
30
50
70
90

0.000
0.374
2.333
3.844
3.844
3.844
3.844
3.844
69.575
89.350

max 

Achieved  [%]

F3

0
1
3
5
10
20
30
50
70
90

297.7
264.1
240.9
208.0
208.0
208.0
208.0
208.0
156.8
144.3

Cut Size

F20 K0.73 K1.00
0.000
0.594
2.333
3.844
3.844
3.844
3.844
3.844
69.575
89.350

0.000
0.545
2.334
3.845
3.846
3.850
3.850
3.850
3.850
3.850

0.000
0.991
2.944
3.846
3.845
3.846
3.845
3.845
3.846
69.598

M
0.001
0.000
0.001
0.001
0.000
0.001
0.001
0.001
41.178
47.370

I

F3 F20 K0.73K1.00

0.000 136
0.388
87
0.071
76
0.102
61
3.169
61
3.866
61
3.866
61
3.866
61
66.537 46
70.315 42

Running Time [s]

2489.1
274.7
720.8
1262.3
2073.7
249.0
249.1
248.8
249.6
249.2

2560.7
279.0
665.0
1251.1
2715.5
3463.3
4176.1
3702.3
4047.7
6359.3

I

119 1342 1344 245 1579
86 109 106 216 406
76
76
69 204 257
61
61
61 255 186
61
61
61 196
81
61
61
61 138
61
61
61
61 232
61
61
61
61 198
61
46
61
61 64414 61
42
61
46 60071 46
Are sides connected?

F20 K0.73 K1.00
1902.0
1717.6
1584.2
1377.5
1377.5
1377.5
1377.5
1377.5
1056.2
965.2

M

M

I

12.2 15.7
12.1 23.6
12.2 31.7
12.4 35.5
12.4 29.7
12.2 45.6
12.3 64.8
12.4 100.7
12.9 158.7
12.8 201.1

F3 F20 K0.73K1.00
•
•
•
•
•
•
•
•
•
•

•
•
•
•
•
•
•
•
•
•

◦
•
•
•
•
•
•
•
•
•

◦
◦
◦
•
•
•
•
•
•
•

M

I

•
◦
•
◦
•
•
•
•
◦
◦

◦
◦
◦
◦
•
•
•
•
•
•

Table 2: Results for the DIMACS USA graph.
However, the best of at least 10 K0.61 runs wins against one K1.00 run with a bad seed. This
effect explains the observed variance. Both, the running times of K1.0 and K0.61, are very
high but for different reasons. K0.61 is slow because of the numerous repetitions on each level.
However, K1.00 is slow because the newer KaHip version is significantly slower for  = 20% than
the older versions. We will see this effect in greater detail in Section 6.3.
F3 vs F20 vs F100 It is not always clear which of F3, F20, or F100 gives the best results.
F3 is most of the time slightly worse. This suggests that three source-target pairs are enough to
get good separators most of the time but not enough to be fully reliable. A bad random seed
can result in good separators being missed. The difference between F20 and F100 in terms of
order quality is nearly negligible. This means that F20 and F100 find nearly always at least
very similar separators. We conclude that there is no real advantage of going from 20 sourcetarget pairs to 100 on road graphs. 20 source-target pairs are enough to be quality wise nearly
independent of the random seed used.

6.3

Pareto Cut Set Experiments

In the previous experiment, we have demonstrated that FlowCutter produces the best contraction orders. In this section, we look at the Parteo-cut sets of five graphs in more detail. These
are the DIMACS California and Nevada, Colorado, USA, and Europe graphs and a Central
European subgraph.
21

Experimental Setup For each of these graphs we report the results in a table similar to
Table 2. With the exception of FlowCutter, we ran each of the algorithms for various maximum
imbalance input parameters (max  column), effectively sampling the Pareto-set computed by
each partitioner. We report the imbalance of the produced cut. This achieved imbalance can be
smaller than the input parameter which is only a maximum. We further report the size of each
cut and indicate whether both sides of the cut form connected subgraphs. Finally, we report
the running time needed to compute each cut. To compute all reported cuts, i.e., the sampled
Pareto-set, all partitioners except FlowCutter need the sum over all reported running times.
For FlowCutter we use a slightly different setup. We compute a set of Pareto-cuts using
FlowCutter and then pick the best cut from this set that has an imbalance below the requested
maximum. This means that for FlowCutter one can compute all reported cuts within the time
needed to compute the cut for the input parameter max  = 0.
PUNCH In [16], a competing algorithm named PUNCH was introduced. Unfortunately, we
do not have access to an implementation of it. We therefore cannot perform experiments with
this algorithm. However, for the USA and Europe graphs, the original authors [16] report cut
sizes for an imbalance of 3%. In their experimental setup, PUNCH is run 100 times with varying
random seeds. On average, PUNCH finds a cut with 130 edges for Europe and 70 edges for the
USA. The minimum cut size over 100 runs is 129 respectively 69 edges. K1.0 finds a cut with
130 edges for Europe graph and 69 edges for the USA. We conclude, that the performance of
PUNCH is comparable in terms of quality to K1.0.
Instance Selection Selecting meaningful and representative testing instances is difficult as
can be seen from Table 2. For the imbalance between 20% and 50% all partitioners with the
exception of Metis find a cut of the same size. One can argue that this imbalance range is the
most relevant for our application. It is therefore hard to argue, based on this experiment, whether
one partitioner is better than another in terms of cut quality because they are all quasi the same.
All cuts with 61 edges divide the USA along the Mississippi river into east and west. This cut is
so pronounced that nearly all partitioners manage to find it. However, we cannot conclude from
this experiment that all partitioners are interchangeable in terms of quality. This experiment
only illustrates that the USA graph is in some sense an easy instance and therefore not a good
testing instance. We therefore need to look at subgraphs of the USA to be able to observe the
differences in quality, that definitely exist given the difference in contraction order qualities. We
provide results for the DIMACS California and Nevada graph and the DIMACS Colorado graph
in Tables 3 and 4. We also ran experiments on the DIMACS Europe graph. However, because
of the special geographical topology of Europe, which we discuss in detail in Section 6.4, this
graph is also non-representative. We therefore evaluate the algorithms on a Central European
subgraph induced by nodes with a latitude ∈ [45, 52] and a longitude ∈ [−2, 11]. This subgraph
has about n = 7M nodes and m = 18M arcs.
6.3.1

Discussion for USA

As already outlined, we cannot deduce much from the experimental results for the USA graph.
However, there are a few observations that are interesting nonetheless. Most of these observations are also valid for all other test instance. We will therefore refrain from repeating these
observations when discussing the other graphs.
Limitations of Metis Metis is clearly dominated as it is the only partitioner unable to find
the Mississippi. We can further observe that for imbalances of 70% and above Metis finds huge
cuts. This is most likely a bug in the implementation. Further, while Metis does find a highly

22

balanced cut, it is not perfectly balanced and therefore formally not a valid output for the case
max  = 0.
Limitations of KaHip The running times of K0.73 are comparatively small for imbalances of
20% and higher. This is not the behavior that one would expect from the algorithm description.
The running time is expected to grow with increasing imbalance as it does for K1.00. The reason
for this behavior is the bug that was fixed in version 1.00. Before this version, KaHip would not
do the flow based refinement steps correctly. KaHip was therefore faster but the achieved cuts
can be very strange. This fixed bug is also the reason why computing contraction orders with
K1.00 is so slow.
Different Mississippi cuts Another interesting observation is that while nearly all partitioners are able to find a Mississippi cut, they find different variants of it. All cuts have size 61
but the achieved imbalances vary. FlowCutter finds slightly smaller imbalances than KaHip and
InertialFlow. The cuts found by FlowCutter are therefore marginally better.
Connected Sides FlowCutter guarantees by construction that both sides of each reported
cut are connected. The other partitioners give no such guarantees. This means that the exact
problem variants that they solve are slightly different. We therefore report for each of the other
partitioners whether the cut they find happens to have connected sides. It is interesting that
this is nearly always the case. One of the exceptions is for example the 3% imbalance of K1.00
with 69 edges. This cut is also the only situation where FlowCutter is outperformed in terms
of cut size on the USA graph. However, the sides of this cut are not connected. The cut is
therefore not a valid solution with respect to the exact problem setting solved by FlowCutter.
This explains why it is not found.
Perfectly balanced Cuts Even though it is not useful for our application, it is interesting
to compare the algorithms in terms of perfectly balanced cuts. This is the case when max  = 0
or formulated differently: The number of nodes on each side must not differ by more than one
node. Past research has partially focused on this special case. KaHip even includes a special
postprocessing step called cycle-refinement to reduce the sizes of perfectly balanced cuts [39].
The results are surprising. Metis is not able to find perfectly balanced cuts as the balance of the
achieved cut is larger than required. For this border case the achieved cuts are thus formally
not valid. Even though KaHip includes special code, the achieved cut sizes are large. They even
rival those of InertialFlow, a heuristic that in the case of perfect balance degenerates to sorting
the nodes by longitude and cutting along the median. KaHip’s cycle-refinement clearly does not
work on this kind of graph. Even though FlowCutter was not designed to compute perfectly
balanced cuts, it is capable of doing so. Further these cuts found turn out to be that smallest
among all competitors by a significant margin.
6.3.2

Discussion for California and Nevada

Perfectly balanced cuts We include the DIMACS California & Nevada graph in our benchmark because [14] were able to determine the optimal size of a perfectly balanced cut for this
graph. The optimum is 32 edges. The best cut found by the partitioners evaluated in Table 3
contains 39 edges and was found by FlowCutter. It is therefore off by 7 edges. However, even
with a slight imbalance, i.e., max  = 1%, F3, F20, and K0.73 are able to find a cut with 31
edges. As this cut is smaller than the smallest balanced cut, it is possible that this 31 edge cut
is optimal.

23

max 

F3

0
1
3
5
10
20
30
50
70
90

0.000
0.169
2.293
2.293
2.293
2.293
2.293
2.293
64.522
87.953

Achieved  [%]

Cut Size

F20 K0.73 K1.00
0.000
0.184
2.300
2.293
2.304
2.756
2.768
2.768
2.768
2.768

0.000
1.000
2.303
2.329
2.294
2.293
2.293
2.296
2.296
82.592

max 

0.000
0.169
2.293
2.293
2.293
16.706
16.706
49.058
49.058
89.838

F3

F20 K0.73 K1.00

0
1
3
5
10
20
30
50
70
90

9.5
8.0
7.7
7.7
7.7
7.7
7.7
7.7
7.1
5.3

59.8
53.2
51.0
51.0
51.0
49.6
49.6
43.2
43.2
25.4

M

I

0.000
0.000
0.001
0.005
0.001
0.000
13.936
0.000
41.178
47.370

0.000
0.566
1.112
1.571
0.642
2.656
5.484
40.833
42.591
85.555

F3 F20 K0.73K1.00
42
31
29
29
29
29
29
29
27
20

Running Time [s]

30.8
14.6
24.0
36.4
76.2
15.0
15.5
15.5
15.4
15.6

31.6
14.8
23.5
35.8
70.9
94.5
109.7
137.2
159.6
125.3

39
31
29
29
29
28
28
24
24
14

157
31
29
29
29
30
29
29
29
29

M

I

174
51
36
52
29
61
29
42
29
43
29
41
29
51
29
39
29 4310
19 3711

306
93
64
62
37
29
29
27
26
18

Are sides connected?
M

I

0.8
0.8
0.8
0.8
0.8
0.9
0.8
0.8
0.8
0.9

1.1
1.4
1.7
2.3
2.2
2.4
2.9
3.7
4.9
5.2

F3 F20 K0.73K1.00
•
•
•
•
•
•
•
•
•
•

•
•
•
•
•
•
•
•
•
•

◦
•
•
•
•
•
•
•
•
•

◦
•
•
•
•
•
•
•
•
•

M

I

•
•
•
•
•
◦
•
•
◦
◦

◦
◦
◦
◦
◦
•
•
◦
◦
•

Table 3: Results for the DIMACS California and Nevada.
Cut sizes The sizes of the cuts on California seem to be similar to those of the USA graph.
There is one small and very pronounced cut, the one with 29 edges, which is found by all
partitioniers. However, F20 is able to find a 28 and 24 edge cut for higher imbalances. KaHip
misses these cuts and sticks with the 29 edge cut. It is also interesting that InertialFlow is able
to find a good 29 edge cut with 2.7% imbalance. Unfortunately, it does not find it when the
input parameter is at max  = 3% but at max  = 20%. This means InertialFlow is capable of
finding good cuts, but max  parameters that significantly differ from the desired  have to be
tried.
6.3.3

Discussion for Colorado

Perfectly balanced cuts The authors of [14] were also able to determine the minimum size
of a perfectly balanced cut on the Colorado graph. It has 29 edges. While FlowCutter comes
closest among all the evaluated partitioners, the cut found is again significantly larger by 8
edges. For imbalances in the range of 1% to 3% F20, K0.73, and K1.00 manage to achieve cut
sizes of 29 edges but no cut is perfectly balanced. All of them are therefore suboptimal. For
 = 5% cuts smaller than 29 edges are found.
Cut Sizes In contrast to the USA graph, we observe different cut sizes for the different partitioners on this instance for the relevant imbalances. We can therefore better deduce from this
experiment whether a partitioner is better than another for our specific application. We observe
24

max 

F3

0
1
3
5
10
20
30
50
70
90

0.000
0.308
0.308
0.308
0.308
17.664
22.784
22.784
22.784
88.080

Achieved  [%]

Cut Size

F20 K0.73 K1.00
0.000
0.970
2.999
4.290
9.467
11.761
12.249
9.772
12.000
12.084

0.000
0.023
0.553
0.553
0.550
18.842
27.737
40.630
40.630
81.224

max 

0.000
0.277
0.277
4.263
9.073
19.995
27.606
40.630
57.602
87.330

F3

F20 K0.73 K1.00

0
1
3
5
10
20
30
50
70
90

2.0
1.7
1.7
1.7
1.7
1.3
1.1
1.1
1.1
1.1

12.1
9.9
9.9
9.6
8.1
6.8
5.2
4.5
4.2
3.1

M

I

0.001
0.002
0.000
0.025
0.001
16.671
23.080
42.409
41.177
47.362

0.000
0.088
0.748
0.897
1.413
13.984
23.125
36.365
48.771
81.495

F3 F20 K0.73K1.00
37
31
31
31
31
22
18
18
18
17

Running Time [s]

4.5
2.8
4.0
5.1
9.1
3.2
3.0
3.4
3.5
3.5

3.6
2.7
4.4
7.1
15.7
16.5
23.3
35.2
40.8
24.4

37
29
29
28
23
19
14
12
11
8

74
34
29
27
23
22
20
23
23
20

M

I

49
40
29
39
28
51
28
40
28
47
19 376
14 521
12
14
12 1124
9 856

259
96
70
60
46
27
21
14
12
9

Are sides connected?
M

I

0.1
0.2
0.2
0.1
0.2
0.2
0.2
0.1
0.2
0.2

0.2
0.3
0.3
0.3
0.3
0.3
0.4
0.4
0.5
0.6

F3 F20 K0.73K1.00
•
•
•
•
•
•
•
•
•
•

•
•
•
•
•
•
•
•
•
•

◦
•
•
•
•
•
•
•
•
•

◦
•
•
•
•
•
•
•
•
•

M

I

•
•
•
•
◦
◦
◦
•
◦
◦

◦
◦
◦
◦
◦
•
•
◦
•
•

Table 4: Results for the DIMACS Colorado.
that F20 wins with respect to every imbalance except for max  = 3% and max  = 5% where
K1.00 and K0.73 respectively win by one edge. This demonstrates that FlowCutter is indeed a
heuristic and does not always achieve the optimum. Comparing K1.00 and K0.73 is interesting.
One could expect K1.00 to always win because it is the newer version but this is not the case.
For max  = 1% K1.00 is 5 edges ahead but for max  = 10% K0.73 wins by 5 edges. This can
mean that K1.00 is not always superior to K0.73. Another explanation is that both do not make
enough iterations in their standard configuration to produce results that are reliable, i.e, with
high probability insensitive to the random seed used. Rerunning K1.00 and K0.73 with different
random seeds could change the outcome. The cut sizes of Metis are far from the competitors.
InertialFlow is better than Metis but also clearly dominated.
Running Times Metis and InertialFlow are by an order of magnitude faster but also compute
worse cuts. The comparison between FlowCutter and KaHip is interesting. FlowCutter gets
slower with a decreasing maximum imbalance. However, KaHip gets slower with an increasing
maximum imbalance, i.e., the other way round. A clear ranking is therefore not possible but the
tendency for max imbalances above 10% is that F3 is the fastest, followed by K0.73, followed
by F20, and finally K1.00.

25

max 

F3

0
1
3
5
10
20
30
50
70
90

0.000
0.232
0.232
4.963
6.914
19.419
19.419
19.419
63.775
84.199

max 

Achieved  [%]

F3

0
1
3
5
10
20
30
50
70
90

231.4
230.2
230.2
229.9
225.0
215.7
215.7
215.7
101.8
13.8

Cut Size

F20 K0.73 K1.00
0.000
0.132
0.132
4.894
9.330
10.542
10.542
44.386
66.655
84.199

0.000
0.998
0.457
0.464
0.043
3.139
3.139
3.139
3.139
3.139

0.000
0.916
2.086
1.470
8.862
10.546
10.543
10.547
10.547
10.544

M

I

0.000
0.000
0.000
0.000
0.000
0.000
0.017
33.336
41.178
83.087

0.000
0.089
0.008
0.857
0.375
0.132
7.384
10.542
44.386
84.257

F3 F20 K0.73K1.00
292
275
275
271
243
225
225
225
100
13

Running Time [s]

369.1
80.2
112.5
158.3
338.1
75.5
75.4
75.3
75.5
75.4

315.9
72.2
111.7
206.5
455.1
355.4
395.9
467.4
560.4
633.0

716
245
227
227
228
250
250
250
250
250

I

674 369 1180
216 360 391
207 372 319
208 369 276
207 375 241
162 375 220
162 369 203
162 9881 162
162 14375 155
162
28
17

Are sides connected?

F20 K0.73 K1.00
1390.3
1342.9
1342.9
1319.0
1181.5
1089.5
1089.5
1047.8
591.6
92.8

240
220
220
213
180
162
162
155
86
13

M

M

I

3.3
3.3
3.1
3.3
3.1
3.1
3.1
3.2
3.2
3.3

4.3
7.9
10.2
12.3
16.8
25.6
34.9
47.5
82.8
17.1

F3 F20 K0.73K1.00
•
•
•
•
•
•
•
•
•
•

•
•
•
•
•
•
•
•
•
•

◦
•
•
•
•
•
•
•
•
•

◦
•
•
•
•
•
•
•
•
•

M

I

•
•
•
•
•
◦
•
◦
◦
•

◦
◦
◦
•
◦
•
•
•
•
◦

Table 5: Results for the DIMACS Central Europe graph.
6.3.4

Discussion for Central Europe

Cut sizes In Table 5 we report the results of our experiments for the Central Europe graph.
The most striking observation is that the cut sizes in this graph are larger than those in any of
the USA graphs. This explains why the Europe graph has a higher tree-width and larger search
spaces than the USA graph. It is not immediately clear which cut is the best for our application,
however, the cuts with sizes 180, 162, and 155 seem to offer a good trade-off between cut size
and imbalance. F20 manages to find all of them. K1.00 finds a variant of the 162 edge cut with
a marginally higher imbalance. InertialFlow is able of finding the 162 and the 155 edge cuts.
Unfortunately, as already previously observed we need to set the max  parameter significantly
higher than the imbalance of the cuts for InertialFlow to find them.
Running Times On all of the USA graphs F20 was at least on par with K1.00 in terms of
running time and often even faster. On this graph we see a significant gap of at least a factor 2
for all imbalances below 70%. The explanation is that the running time of FlowCutter does not
only depend on the graph size but also on the cut size. As this graph has larger cuts than the
USA graphs, FlowCutter is slower. KaHip’s running time is not or at least less affected by cut
size and therefore comes out ahead on this graph. However, for our particular application, i.e.,
nested dissection, a running time sensitive to the cut size is a good thing. We have only few top
level cuts with large cuts but many more low level cuts that have tiny cuts. A partitioner that
gets faster, the smaller the cuts become is therefore useful in this scenario as it gets faster on
26

max 

F3

0
1
3
5
10
20
30
50
70
90

0.000
0.930
2.244
2.244
9.453
9.453
9.453
9.453
64.477
72.753

max 

Achieved  [%]

F3

0
1
3
5
10
20
30
50
70
90

508.4
468.6
455.7
455.7
411.5
411.5
411.5
411.5
134.4
7.6

Cut Size

F20 K0.73 K1.00
0.000
0.930
2.244
4.918
9.453
9.453
9.453
42.080
67.497
72.753

0.000
1.000
2.717
2.976
8.092
9.405
9.232
9.232
9.232
9.232

0.000
0.984
2.654
2.985
7.875
7.888
8.216
8.214
32.079
72.753

M

I

0.003
0.003
0.003
0.003
0.003
0.003
0.003
33.336
41.178
70.741

0.000
0.337
0.357
0.171
0.174
7.539
9.060
9.453
64.724
72.753

F3 F20 K0.73K1.00
369
234
221
221
188
188
188
188
58
2

Running Time [s]
F20 K0.73 K1.00
3475.5
3292.7
3215.0
3181.7
2913.3
2913.3
2913.3
949.4
371.9
51.9

1887.5
224.7
317.5
510.2
934.0
198.8
193.6
194.1
193.9
194.1

1893.9
196.9
303.3
524.8
1419.1
1646.2
1569.3
1727.7
1642.2
3411.3

M

I

276 1296 1299 402 1579
234 169 154 398 417
221 130 130 306 340
216 129 129 276 299
188 112 112 460 284
188 126 112 483 229
188 128 111 465 202
58 128 111 31127 188
22 128
86 53365 38
2 128
2
44
2
Are sides connected?

M

I

8.9 11.3
8.9 19.0
8.9 28.0
8.9 33.6
9.0 49.3
8.9 69.9
8.9 94.0
9.1 172.9
9.4 79.0
9.0 18.9

F3 F20 K0.73K1.00
•
•
•
•
•
•
•
•
•
•

•
•
•
•
•
•
•
•
•
•

◦
◦
•
•
◦
◦
◦
◦
◦
◦

◦
•
•
•
◦
◦
◦
◦
◦
•

M

I

◦
•
◦
◦
◦
◦
•
◦
◦
◦

◦
◦
◦
◦
•
◦
•
•
•
•

Table 6: Results for the DIMACS Europe.
the lower levels. This observation also explains why F20 wins against K1.00 in terms of running
time on the Europe graph in the CCH experiment.

6.4

Special Structure of the Europe Graph

We present the results for the Europe graph in Table 6. The reported cut sizes do not follow
the pattern observed on the other graphs. The cuts of F20 are significantly larger than those of
KaHip. Another observation is that most of the cuts found by partitioners except FlowCutter do
not have connected sides. This already hints at the root of the problem. In Figure 6 we visualized
the cuts found. Figure 6a depicts the cut found by KaHip with 112 edges and Figure 6c depicts
the cut found by F20 with 188 edges. Visually these two cuts look very different. To explain
the effect in detail we must first describe some properties of the Europe graph.
Unique Geography Top-level Europe has a unique geographic topology. There is a well
connected center formed by France, Germany, Belgium, Luxembourg, and the Netherlands.
Further, there are four peninsulas. Spain and Portugal are only connected by a comparatively
small piece of land with France. Italy is separated by the rest of Europe by the Alps. Sweden
and Norway are separated by the Baltic Sea from Central Europe. They are only connected to
Denmark by a highway bridge in Kopenhagen. This bridge is also the cut with 2 edges with
72% imbalance found by several partitioners. Great Britain is separated by the North Sea and
is only connected to the continent using ferries, which are treated as roads in the benchmark
27

(a) K0.76

(b) F with guidance

(c) F20

Figure 6: Various top-level Europe cuts.
dataset. There are further ferries between Spain and England, and between Spain and Italy.
However, there are no ferries from or to Scandinavia.
Structure of KaHip Cuts The KaHip cut with 112 edges separates Central Europe from
its peninsulas. The sides are not connected because there is no path from Great Britain to
Scandinavia. The KaHip cut with 129 edges with connected sides further separates Denmark
from Germany. The sides of the cut are connected, as there is a ferry from England to Denmark
and a bridge from Denmark to Sweden.
Structure of FlowCutter Cuts The FlowCutter cut is structurally very different. FlowCutter separates Central Europe along the Rhine river and the Alps. FlowCutter cannot find
the 112 edge cut because its sides are not connected. Further, it does not find the 129 edge cut
because the shape of this cut is very different from what the employed piercing heuristic expects.
KaHip vs FlowCutter At first glance, KaHip seems to be better than FlowCutter on this
instance. However, this is not consistent with our observation that FlowCutter produces better
contraction orders. The explanation is that, as we consider a recursive bisection, the question is
not whether Central Europe must be cut along the Rhine river, but at which recursion level we
do it. FlowCutter does it at the top level, whereas KaHip does it at a lower level. It is unclear
which approach is better. We will investigate this question in detail below. However, before we
answer this question we explore how we can modify FlowCutter to find a cut similar to the one
found by KaHip.
Adapting FlowCutter One can regard the balanced 112 edge cut of KaHip as union of four
smaller edge cuts with a higher imbalances. There is one cut for each peninsula. Repeatedly
cutting of each peninsula on consecutive levels of the recursion is equivalent with cutting them
all in one level. The question is therefore whether FlowCutter is able to find one of the peninsula
cuts and this is indeed the case. FlowCutter finds the cut with 2 edges that separates Scandinavia
from the rest. However, FlowCutter refrains from choosing this cut from the Pareto-set because
we have a hard bound on a maximum imbalance of at most 60%.
Another option to help FlowCutter is to handpick source and target nodes. We selected
the nodes which are closed to the coordinates given in Table 7 and used these as input to
FlowCutter. These coordinates are not magic numbers. They represent positions chosen at the
extremities of the peninsulas and in the center of Central Europe. Most humans are able to
deduce this information from looking at a Europe map. With this setup we were not able to
find the 112 edge cut with 7.9% imbalance found by KaHip. However, we were able to find
another cut with a seemingly better trade-off. This new cut is depicted in 6b. It has 87 edges
and 15% imbalance. The smaller cut results from placing Austria on the other side of the cut

28

Lat Lon

Place

Source 49.0 8.4 Karlsruhe
41.0
38.7
Target
53.5
59.2

16.9
Bari
-9.1 Lisbon
-2.8 Liverpool
18.0 Stockholm

Table 7: Handpicked source and target nodes.
Search Space
Nodes

#Arcs

Arcs [·103 ] in CCH #Tri. Tw.

Avg. Max. Avg. Max.
F3
F20
F100

Up.

[·106 ] [·106 ] Bd.

734.1 1 159 140.2
616.0 1 102 102.8
622.6 1 105 104.8

312
268
239

60.3 519.4 531
58.8 459.6 455
58.8 459.4 449

F3+H 625.1 1 151 106.2
F20+H 601.2 1 064 98.9
F100+H 600.6 1 065 98.6

262
261
250

60.2 509.2 439
58.8 456.9 444
58.8 454.4 444

Table 8: Contraction Order Experiments on the DIMACS Europe graph. F3, F20, F100 are
the default FlowCutter variants that use a top-level cut along the Rhine river. F3+H, F20+H,
F100+H use a handpicked top-level cut separating Central Europe from the peninsulas.
compared to the 112 edge cut of KaHip and from some minor improvements along the other
borders. KaHip is incapable of finding this cut.
The Best Top-level Cut We have shown that with a bit of help it is possible to push
FlowCutter towards computing a small cut that separates the peninsulas. Now, we will answer
the question whether this a better top-level cut than the 188 edge cut found by the default
FlowCutter configuration. We derive an 87 node separator from the 87 edge cut and place these
nodes at the end of the contraction order manually. We then run FlowCutter on the resulting
sides recursively without any further manual guidance. In Table 8 we report the characteristics
of the so obtained orders. The new orders are marked with “+H”, indicating human interaction.
We compare them with the default FlowCutter orders. The new orders seem to be slightly
superior with respect to every criteria except the maximum number of arcs in the search space
where the default FlowCutter orders seem to win. Further, the orders seem to produce a similar
number of edges in the CCH regardless of the top-level cut used. However, the differences in
order quality are very minor. We observe with respect to no criterion a difference that is larger
than 2%. This difference can be due to a peninsula top-level cut being slightly better. However,
another explanation is that FlowCutter finds better cuts on the lower levels because a difficult
to find peninsula cut was eliminated manually. In either case, the differences are so small that
we decided that it is not worthwhile to automatize the selection of a top level peninsula cut.

6.5

Walshaw Benchmark Set

A popular set of graph partitioning benchmark instances is maintained by Walshaw [44]. The
data contains 34 graphs and solutions to the edge-bisection problem with non-connected sides
29

minimum edges in cut for
graph

running

algorithm  = 0%  = 1%  = 3%  = 5%

time [s]

144
F20
144K nodes F100
1074K edges Reference

6 649
6 515
6 486

6 608
6 479
6 478

6 514
6 456
6 432

3elt
F20
4720 nodes F100
13K edges Reference

90*
90*
90*

89
89
89

87
87
87

87
87
87

0.36
1.87

F20
F100
Reference

149
139*
139*

138
138
138

137
137
137

137
137
137

1.97
9.50

598a
F20
110K nodes F100
741K edges Reference

2 417
2 400
2 398

2 390
2 388
2 388

2 367
2 367
2 367

2 336
2 336
2 336

545.69
2 675.32

auto
F20
10 609
448K nodes F100
10 549
3314K edges Reference 10 103

10 283
10 283
9 949

9 890
9 823
9 673

9 450 13 445.66
9 450 66 249.82
9 450

bcsstk30 F20
28K nodes F100
1007K edges Reference

6 347
6 347
6 335

6 251
6 251
6 251

6 251
6 251
6 251

245.65
1 230.27

bcsstk33 F20
10 220 10 097 10 064
8738 nodes F100
10 177 10 097 10 064
291K edges Reference 10 171 10 097 10 064

9 914
9 914
9 914

118.38
573.02

4elt
15K nodes
45K edges

brack2
F20
62K nodes F100
366K edges Reference

6 454
6 408
6 394

6 472 2 423.82
6 366 10 437.91
6 345

742
742
731*

708
708
708

684
684
684

660
660
660

58.13
283.99

crack
10K nodes
30K edges

F20
F100
Reference

184
184
184

183
183
183

182
182
182

182
182
182

2.17
10.97

cs4
22K nodes
43K edges

F20
F100
Reference

381
372
369

371
370
366

367
365
360

360
357
353

11.68
58.11

cti
16K nodes
48K edges

F20
F100
Reference

342
339
334

318
318
318

318
318
318

318
318
318

6.10
30.55

fe_4elt2
11K nodes
32K edges

F20
F100
Reference

130*
130*
130*

130
130
130

130
130
130

130
130
130

1.86
9.19

Table 9: Performance on the Walshaw benchmark set, part 1. “Reference” is the best known
bisection for the graph as maintained by Walshaw. A “*” marks solutions for which optimality
has been shown.

30

graph

algorithm

minimum edges in cut for

running

 = 0%  = 1%  = 3%  = 5%

time [s]

fe_ocean FlowCutter 20
143K nodes FlowCutter 100
409K edges Reference

504
483
464

431
408
387

311
311
311

311
311
311

89.70
418.60

fe_rotor
FlowCutter 20
99K nodes FlowCutter 100
662K edges Reference

2 115
2 106
2 098

2 091
2 067
2 031

1 959
1 959
1 959

1 948
1 940
1 940

334.58
1 636.78

FlowCutter 20
FlowCutter 100
Reference

386
386
386

386
386
386

384
384
384

384
384
384

5.98
30.84

fe_tooth FlowCutter 20
78K nodes FlowCutter 100
452K edges Reference

3 852
3 836
3 816

3 841
3 832
3 814

3 814
3 790
3 788

3 773
3 773
3 773

413.48
2 067.54

finan512
FlowCutter 20
74K nodes FlowCutter 100
261K edges Reference

162*
162*
162*

162
162
162

162
162
162

162
162
162

8.11
39.01

m14b
FlowCutter 20
214K nodes FlowCutter 100
1679K edges Reference

3 858
3 836
3 836

3 826
3 826
3 826

3 823
3 823
3 823

80
80
79

79
77
75

73
71
71

fe_sphere
16K nodes
49K edges

3 805 2 115.07
3 804 10 512.24
3 802
65
65
65

2.98
14.55

vibrobox FlowCutter 20
10 614 10 356 10 356 10 356
12K nodes FlowCutter 100 10 365 10 310 10 310 10 310
165K edges Reference
10 343 10 310 10 310 10 310

139.90
680.76

t60k
60K nodes
89K edges

FlowCutter 20
FlowCutter 100
Reference

wave
FlowCutter 20
156K nodes FlowCutter 100
1059K edges Reference

8 734
8 716
8 677

8 734
8 673
8 657

8 734
8 650
8 591

8 724 2 723.12
8 590 13 583.59
8 524

whitaker3 FlowCutter 20
9800 nodes FlowCutter 100
28K edges Reference

127*
127*
127*

126
126
126

126
126
126

126
126
126

1.49
7.00

wing
FlowCutter 20
62K nodes FlowCutter 100
121K edges Reference

790
790
789

790
790
784

790
781
773

790
773
770

80.11
401.82

wing_nodal FlowCutter 20
10K nodes FlowCutter 100
75K edges Reference

1 767
1 743
1 707

1 764
1 740
1 695

1 715
1 710
1 678

1 691
1 688
1 668

27.02
134.05

Table 10: Performance on the Walshaw benchmark set, part 2.

31

and maximum imbalance values of  = 0%,  = 1%,  = 3%, and  = 5%. These archived
solutions are the best cuts that any partitioner has found so far. A few of them were even
proven to be optimal [14]. Comparing against these archived solutions allows us to compare
FlowCutter quality-wise against the state of the art. We want to stress that this state of the
art was computed by a large mixture of algorithms with an even larger set of parameters that
may have been chosen in instance-dependent ways. We compare this against a single algorithm
with a single set of parameters. Further FlowCutter was designed for higher imbalances than
5%. It was not tuned for the cases with a lower imbalance. FlowCutter only computes cuts with
connected sides. We therefore filter out all graphs that are either not connected or where the
archived  = 0-solution has non-connected sides. Of the 34 graphs only 24 remain. The results
are reported in Tables 9 and 10.
For  = 5% there are only six graphs where FlowCutter does not match the best known cut
quality. These are: “144”, “cs4”, “m14b”, “wave”, “wing”, and “wing_nodal”. For three of these
graphs, FlowCutter finds cuts that are larger by a negligible amount of at most 5 edges. For the
other three, the cuts found are larger but are still close to the best known solutions. For lower
imbalances, the results are not quite as good but still very close to the best known solutions.
In terms of running time the results are more mixed. Some cuts are found very quickly,
while FlowCutter needs a significant amount of time on others. This is due to the fact that its
running time is in O(cm). If both, the cut size c and the edge count m, are large, then O(cm)
is large. However, for graphs with small cuts the algorithm scales nearly linearly in the graph
size.

7

Conclusion

We introduce FlowCutter, a graph bisection algorithm that optimizes balance and cut size in
the Pareto sense. The core algorithm computes small, balanced edge cuts separating two input
nodes s and t. Upon this core algorithm, we build algorithms to compute overall small, balanced
edges cuts independent of an st-pair specified in the input. We further extend our algorithm to
compute small balanced node separators. By combining FlowCutter with a nested dissectionbased strategy, we compute contraction orders (also called elimination or minimum fill-in orders).
We show that our orders beat the state-of-the-art in terms of quality on road graphs. We evaluate
the quality of our orders by directly applying them in the context of Customizable Contraction
Hierarchies, a speedup technique for shortest paths. Further, we show that FlowCutter manages
to equate the best known cuts for many instances of the Walshaw benchmark set, demonstrating
that FlowCutter is applicable beyond just bisecting road graphs. Finally, we use FlowCutter
to compute tree-decompositions of small width. To evaluate the performance of our method,
we submitted FlowCutter to the PACE2016 challenge [13], where it won the first place in the
corresponding sequential track. This demonstrates that FlowCutter works well on a broad class
of graphs. The source code of the PACE 2016 submission is available at [45].
Future Work We show that FlowCutter is an excellent tool to be used within shortest path
acceleration techniques on road graphs. Luckily, the developed techniques seem also useful in
other domains. Experimental evaluations that take domain specific requirements into account
would be interesting venue for future research. For example, our secondary piercing heuristic
could be swapped out with one that uses information that is only available in certain applications.
Another open question is how to adapt FlowCutter to graphs that have weighted nodes or
weighted edges or even both.
We use a nested dissection scheme to compute contraction orders with FlowCutter as bisection algorithm. This seems somewhat wasteful as in this setup FlowCutter computes a large
set of cuts but we only use one of them and then discard the others. In the deeper levels of
the recursion FlowCutter will then likely recompute some of the discarded cuts. Adapting the
32

nested dissection scheme in a way that utilizes several cuts from each set could significantly
improve the running time.
FlowCutter needs two initial nodes on separate sides of the cut. Currently these are determined by random sampling. A better selection strategy could decrease the number of samples
needed.
Acknowledgment: We thank Roland Glantz for helpful discussions.

References
[1] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory,
Algorithms, and Applications. Prentice Hall, 1993.
[2] David A. Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner. Graph Partitioning and Graph Clustering: 10th DIMACS Implementation Challenge, volume 588.
American Mathematical Society, 2013.
[3] Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller–Hannemann, Thomas
Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Route planning in transportation networks. Technical Report abs/1504.05140, ArXiv e-prints, 2016. To appear in
LNCS Volume on Algorithm Engineering, Lasse Kliemann and Peter Sanders (eds.).
[4] Reinhard Bauer, Tobias Columbus, Bastian Katz, Marcus Krug, and Dorothea Wagner.
Preprocessing speed-up techniques is hard. In Proceedings of the 7th Conference on Algorithms and Complexity (CIAC’10), volume 6078 of Lecture Notes in Computer Science,
pages 359–370. Springer, 2010.
[5] Reinhard Bauer, Tobias Columbus, Ignaz Rutter, and Dorothea Wagner. Search-space
size in contraction hierarchies. In Proceedings of the 40th International Colloquium on
Automata, Languages, and Programming (ICALP’13), volume 7965 of Lecture Notes in
Computer Science, pages 93–104. Springer, 2013.
[6] Philip A. Bernstein and Nathan Goodman. Power of natural semijoins. SIAM Journal on
Computing, 10(4):751–771, 1981.
[7] Jean Blair and Barry Peyton. An introduction to chordal graphs and clique trees. In Graph
Theory and Sparse Matrix Computation, volume 56 of The IMA Volumes in Mathematics
and its Applications, pages 1–29. Springer, 1993.
[8] Hans L. Bodlaender. A tourist guide through treewidth. Acta Cybernetica, 11:1–21, 1993.
[9] Hans L. Bodlaender. Treewidth: Structure and algorithms. In Proceedings of the 14th International Colloquium on Structural Information and Communication Complexity, volume
4474 of Lecture Notes in Computer Science, pages 11–25. Springer, 2007.
[10] Hans L. Bodlaender, John R. Gilbert, Hjalmtyr Hafsteinsson, and Ton Kloks. Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. Journal of Algorithms,
18(2):238–255, March 1995.
[11] Paul Bonsma. Most balanced minimum cuts. Discrete Applied Mathematics, 158(4):261–
276, 2010.
[12] Bruno Courcelle. The monadic second-order logic of graphs. i. recognizable sets of finite
graphs. Information and Computation, 85(1):12–75, March 1990.

33

[13] Holger Dell, Thore Husfeldt, Bart M. Jansen, Petteri Kaski, Christian Komusiewicz, and
Frances Rosamond. The first parameterized algorithms and computational experiments
challenge. In 11th International Symposium on Parameterized and Exact Computation,
Leibniz International Proceedings in Informatics, pages 30:1–30:9, 2016.
[14] Daniel Delling, Daniel Fleischman, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F.
Werneck. An exact combinatorial algorithm for minimum graph bisection. Mathematical
Programming, 153(2):417–458, November 2015.
[15] Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Customizable
route planning in road networks. Transportation Science, 51(2):566–591, 2017.
[16] Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck. Graph
partitioning with natural cuts. In 25th International Parallel and Distributed Processing
Symposium (IPDPS’11), pages 1135–1146. IEEE Computer Society, 2011.
[17] Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson, editors. The Shortest
Path Problem: Ninth DIMACS Implementation Challenge, volume 74 of DIMACS Book.
American Mathematical Society, 2009.
[18] Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Fast exact shortest path and distance queries on road networks with parametrized costs. In Proceedings of the 23rd ACM
SIGSPATIAL International Conference on Advances in Geographic Information Systems,
pages 66:1–66:4. ACM Press, 2015.
[19] Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Customizable contraction hierarchies.
ACM Journal of Experimental Algorithmics, 21(1):1.5:1–1.5:49, April 2016.
[20] Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische
Mathematik, 1(1):269–271, 1959.
[21] Lester R. Ford, Jr. and Delbert R. Fulkerson. Maximal flow through a network. Canadian
Journal of Mathematics, 8:399–404, 1956.
[22] Lester R. Ford, Jr. and Delbert R. Fulkerson. Flows in Networks. Princeton University
Press, 1962.
[23] Delbert R. Fulkerson and O. A. Gross. Incidence matrices and interval graphs. Pacific
Journal of Mathematics, 15(3):835–855, 1965.
[24] Michael R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some simplified N Pcomplete graph problems. Theoretical Computer Science, 1:237–267, 1976.
[25] Alan George. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis, 10(2):345–363, 1973.
[26] Alan George and Joseph W. Liu. The evolution of the minimum degree ordering algorithm.
SIAM Review, 31(1):1–19, 1989.
[27] John R. Gilbert and Robert Tarjan. The analysis of a nested dissection algorithm. Numerische Mathematik, 50(4):377–404, July 1986.
[28] Michael Hamann and Ben Strasser. Graph bisection with pareto-optimization. Technical
report, ArXiv e-prints, 2015.
[29] Michael Hamann and Ben Strasser. Graph bisection with pareto-optimization. In Proceedings of the 18th Meeting on Algorithm Engineering and Experiments (ALENEX’16), pages
90–102. SIAM, 2016.
34

[30] Martin Holzer, Frank Schulz, and Dorothea Wagner. Engineering multilevel overlay graphs
for shortest-path queries. ACM Journal of Experimental Algorithmics, 13(2.5):1–26, December 2008.
[31] John E. Hopcroft and Robert E. Tarjan. Efficient algorithms for graph manipulation.
Communications of the ACM, 16(6):372–378, June 1973.
[32] Cecil Huang and Adnan Darwiche. Inference in belief networks: A procedural guide. International Journal of Approximate Reasoning, 15(3):225–263, October 1996.
[33] Ananth V. Iyer, H. Donald Ratliff, and Gopalakrishnan Vijayan. Optimal node ranking of
trees. Information Processing Letters, 28(5):225–229, August 1988.
[34] George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning
irregular graphs. SIAM Journal on Scientific Computing, 20(1):359–392, 1999.
[35] Frank Thomson Leighton and Satish Rao. Multicommodity max-flow min-cut theorems
and their use in designing approximation algorithms. Journal of the ACM, 46(6):787–832,
1999.
[36] Richard J. Lipton, Donald J. Rose, and Robert Tarjan. Generalized nested dissection.
SIAM Journal on Numerical Analysis, 16(2):346–358, April 1979.
[37] Harry M. Markowitz. The elimination form of the inverse and its application to linear
programming. Management Science, 3(3):255–269, April 1957.
[38] Alex Pothen. The complexity of optimal elimination trees. Technical report, Pennsylvania
State University, 1988.
[39] Peter Sanders and Christian Schulz. Think locally, act globally: Highly balanced graph partitioning. In Proceedings of the 12th International Symposium on Experimental Algorithms
(SEA’13), volume 7933 of Lecture Notes in Computer Science, pages 164–175. Springer,
2013.
[40] Peter Sanders and Christian Schulz. Advanced multilevel node separator algorithms. In
Proceedings of the 15th International Symposium on Experimental Algorithms (SEA’16),
volume 9685 of Lecture Notes in Computer Science, pages 294–309. Springer, 2016.
[41] Alejandro A. Schæffer. Optimal node ranking of trees in linear time. Information Processing
Letters, 33:91–96, November 1989.
[42] Aaron Schild and Christian Sommer. On balanced separators in road networks. In Proceedings of the 14th International Symposium on Experimental Algorithms (SEA’15), Lecture
Notes in Computer Science, pages 286–297. Springer, 2015.
[43] Frank Schulz, Dorothea Wagner, and Karsten Weihe. Dijkstra’s algorithm on-line: An
empirical case study from public railroad transport. ACM Journal of Experimental Algorithmics, 5(12):1–23, 2000.
[44] A. J. Soper, Chris Walshaw, and Mark Cross. A combined evolutionary search and multilevel
optimisation approach to graph partitioning. Journal of Global Optimization, 29(2):225–
241, 2004.
[45] Ben Strasser. Source code of pace 2016 flowcutter submission. Uploaded to github at
https://github.com/ben-strasser/flow-cutter-pace16, 2016.

35

[46] Dorothea Wagner and Frank Wagner. Between min cut and graph bisection. In Proceedings
of the 18th International Symposium on Mathematical Foundations of Computer Science
(MFCS’93), volume 711 of Lecture Notes in Computer Science, pages 744–750, London,
UK, 1993. Springer.
[47] Michael Wegner. Finding small node separators. Bachelor thesis, Karlsruhe Institute of
Technology, October 2014.

36

