Contemporary Mathematics

Volume 588, 2013

http://dx.doi.org/10.1090/conm/588/11700

High quality graph partitioning

Peter Sanders and Christian Schulz

Abstract. We present an overview over our graph partitioners KaFFPa (Karl-

sruhe Fast Flow Partitioner) and KaFFPaE (KaFFPa Evolutionary). KaFFPa

is a multilevel graph partitioning algorithm which on the one hand uses novel

local improvement algorithms based on max-flow and min-cut computations

and more localized FM searches and on the other hand uses more sophisticated

global search strategies transferred from multi-grid linear solvers. KaFFPaE is

a distributed evolutionary algorithm to solve the Graph Partitioning Problem.

KaFFPaE uses KaFFPa and provides new effective crossover and mutation

operators. By combining these with a scalable communication protocol we

obtain a system that is able to improve the best known partitioning results for

many inputs.

1. Introduction

Problems of graph partitioning arise in various areas of computer science, en-

gineering, and related fields. For example in route planning, community detection

in social networks and high performance computing. In many of these applications

large graphs need to be partitioned such that there are few edges between blocks

(the elements of the partition). For example, when you process a graph in parallel

on k processors you often want to partition the graph into k blocks of about equal

size so that there is as little interaction as possible between the blocks. In this

paper we focus on a version of the problem that constrains the maximum block size

to (1+ ) times the average block size and tries to minimize the total cut size, i.e.,

the number of edges that run between blocks. It is well known that this problem

is NP-complete [5] and that there is no approximation algorithm with a constant

ratio factor for general graphs [5]. Therefore mostly heuristic algorithms are used in

practice. A successful heuristic for partitioning large graphs is the multilevel graph

partitioning (MGP) approach depicted in Figure 1 where the graph is recursively

contracted to achieve smaller graphs which should reflect the same structure as the

input graph. After applying an initial partitioning algorithm to the smallest graph,

the contraction is undone and, at each level, a local refinement method is used to

improve the partitioning induced by the coarser level.

Although several successful multilevel partitioners have been developed in the

last 13 years, we had the impression that certain aspects of the method are not

well understood. We therefore have built our own graph partitioner KaPPa [13]

2010 Mathematics Subject Classification. Primary 68W40, 68W10, 90C27, 05C70.

Partially supported by DFG SA 933/10-1.

c 2013 American Mathematical Society

1