2 PETER SANDERS AND CHRISTIAN SCHULZ

input

graph

... ...

initial

contraction

phase

refinement

phase

local improvement

uncontract

partitioning

contract

match

output

partition

Figure 1. Multilevel graph partitioning.

(Karlsruhe Parallel Partitioner) with focus on scalable parallelization. Somewhat

astonishingly, we also obtained improved partitioning quality through rather simple

methods. This motivated us to make a fresh start putting all aspects of MGP on

trial. This paper gives an overview over our most recent work, KaFFPa [22] and

KaFFPaE [21]. KaFFPa is a classical matching based graph partitioning algorithm

with focus on local improvement methods and overall search strategies. It is a

system that can be configured to either achieve the best known partitions for many

standard benchmark instances or to be the fastest available system for large graphs

while still improving partitioning quality compared to the previous fastest system.

KaFFPaE is a technique which integrates an evolutionary search algorithm with

our multilevel graph partitioner KaFFPa and its scalable parallelization. It uses

novel mutation and combine operators which in contrast to previous evolutionary

methods that use a graph partitioner [8,23] do not need random perturbations of

edge weights. The combine operators enable us to combine individuals of different

kinds (see Section 5 for more details). Due to the parallelization our system is able

to compute partitions that have quality comparable or better than previous entries

in Walshaw’s well known partitioning benchmark within a few minutes for graphs

of moderate size. Previous methods of Soper et. al [23] required runtimes of up to

one week for graphs of that size. We therefore believe that in contrast to previous

methods, our method is very valuable in the area of high performance computing.

The paper is organized as follows. We begin in Section 2 by introducing basic

concepts which is followed by related work in Section 3. In Section 4 we present

the techniques used in the multilevel graph partitioner KaFFPa. We continue

describing the main components of our evolutionary algorithm KaFFPaE in Sec-

tion 5. A summary of extensive experiments to evaluate the performance of the

algorithm is presented in Section 6. We have implemented these techniques in the

graph partitioner KaFFPaE (Karlsruhe Fast Flow Partitioner Evolutionary) which

is written in C++. Experiments reported in Section 6 indicate that KaFFPaE is

able to compute partitions of very high quality and scales well to large networks

and machines.

2. Preliminaries

2.1. Basic concepts. Consider an undirected graph G = (V, E, c, ω) with

edge weights ω : E → R 0, node weights c : V → R≥0, n = |V |, and = |E|.

We extend c and ω to sets, i.e., c(V ) :=

∑

v∈V

c(v) and ω(E ) :=

∑m

e∈E

ω(e).

Γ(v) := {u : {v, u} ∈ E} denotes the neighbors of v. We are looking for blocks

of nodes V1,...,Vk that partition V , i.e., V1 ∪ · · · ∪ Vk = V and Vi ∩ Vj = ∅ for

i = j. The balancing constraint demands that ∀i ∈ {1..k} : c(Vi) ≤ Lmax :=