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
Previous Page Next Page