arXiv:1702.01692v1 [] 6 Feb 2017

Distributed Evolutionary k-way Node Separators∗
Peter Sanders

Christian Schulz

Karlsruhe Institute of Technology
Karlsruhe, Germany
sanders@kit.edu

Karlsruhe Institute of Technology
Karlsruhe, Germany and University of Vienna
Vienna, Austria
christian.schulz@univie.ac.at

Darren Strash

Robert Williger

Colgate University
Hamilton, USA
dstrash@colgate.edu

Karlsruhe Institute of Technology
Karlsruhe, Germany
williger@ira.uka.de

ABSTRACT
Computing high quality node separators in large graphs is
necessary for a variety of applications, ranging from divideand-conquer algorithms to VLSI design. In this work, we
present a novel distributed evolutionary algorithm tackling
the k-way node separator problem. A key component of
our contribution includes new k-way local search algorithms
based on maximum flows. We combine our local search with
a multilevel approach to compute an initial population for
our evolutionary algorithm, and further show how to modify
the coarsening stage of our multilevel algorithm to create effective combine and mutation operations. Lastly, we combine
these techniques with a scalable communication protocol,
producing a system that is able to compute high quality
solutions in a short amount of time. Our experiments against
competing algorithms show that our advanced evolutionary
algorithm computes the best result on 94% of the chosen
benchmark instances.

KEYWORDS
graph partitioning, node separators, max-flow min-cut

1

INTRODUCTION

Given a graph G = (V, E), the k-way node separator problem
is to find a small separator S ⊂ V , and k disjoint subsets of
V , V1 , . . . , Vk called blocks, such that no edgesSexist between
two different blocks Vi and Vj (i =
6 j) and V = i Vi ∪S. The
objective is to minimize the size of the separator S or, depending on the application, the cumulative weight of its nodes,
while the blocks Vi are balanced. Note that removing the set
S from the graph results in at least k connected components.
Many algorithms rely on small node separators. For example, small balanced separators are a popular tool in divideand-conquer strategies [2, 18, 20], are useful to speed up the
computations of shortest paths [7, 8, 28], are necessary in
scientific computing to compute fill reducing orderings with
nested dissection algorithms [13] or in VLSI design [2, 18].
∗

This work was partially supported by DFG grants SA 933/11-1.

Finding a balanced node separator is NP-hard for general
graphs even if the maximum node degree is three [4, 12].
Therefore, heuristic and approximation algorithms are used
in practice to find small node separators. The most commonly
used method to solve the node separator problem on large
graphs in practice is the multilevel approach. During a
coarsening phase, a multilevel algorithm reduces the graph
size by iteratively contracting the nodes and edges of G until
the graph is small enough to compute a node separator by
some other (presumably time consuming) algorithm. A node
separator of the input graph is then constructed by iteratively
uncontracting the graph, transferring the solution to this finer
graph, and then applying local search algorithms to improve
the solution.
Although current solvers are typically fast enough for most
applications, they unfortunately produce separators of low
solution quality. This may be acceptable in applications that
use a separator just once, however, many applications first
compute a separator as a preprocessing step, and then rely
on a high-quality separator for speed in later stages. This is
true in VLSI design [2, 18], where even small improvements
in separator size can have a large impact on computation
time and production costs. High-quality node separators can
also speed up shortest path queries in road networks, for
example, in customizable contraction hierarchies [8], where
smaller node separators yield better node orderings that are
repeatedly used to answer shortest path queries. The cost for
computing one high quality node separator is then amortized
over a many shortest path queries. Hence, our focus is on
solution quality in this work.

1.1

Our Results

The main contribution of this paper is a technique that
integrates an evolutionary search algorithm with a novel
multilevel k-node separator algorithm and its scalable parallelization. We present novel mutation and combine operators
for the problem which are based on the multilevel scheme.
Due to the coarse-grained parallelization, our system is able
to compute separators that have high quality within a few
minutes for graphs of moderate size.

Peter Sanders, Christian Schulz, Darren Strash, and Robert Williger

2 PRELIMINARIES
2.1 Basic Concepts
Throughout this paper, we consider an undirected graph
G = (V = {0, . . . , n − 1}, E) with n = |V |, and m = |E|.
Γ(v) := {u : {v, u} ∈ E} denotes the neighborhood of a node
v. A graph S = (V 0 , E 0 ) is said to be a subgraph of G = (V, E)
if V 0 ⊆ V and E 0 ⊆ E ∩ (V 0 × V 0 ). We call S an induced
subgraph when E 0 = E ∩(V 0 ×V 0 ). For a set of nodes U ⊆ V ,
G[U ] denotes the subgraph induced by U .
The graph partitioning problem, which is closely related to
the node separator problem, asks for blocks of nodes V1 ,. . . ,Vk
that partition V (i.e., V1 ∪· · ·∪Vk = V and Vi ∩Vj = ∅ for i =
6
j). A balancing constraint demands that ∀i ∈ {1..k} : |Vi | ≤
Lmax := (1+)d|V |/ke for some parameter .PIn this case, the
objective is often to minimize the total cut
i<j |Eij | where
Eij := {{u, v} ∈ E : u ∈ Vi , v ∈ Vj }. The set of cut edges is
also called edge separator. An abstract view of the partitioned
graph is the so called quotient graph, where nodes represent
blocks and edges are induced by connectivity between blocks.
The node separator problem asks to find blocks, V1 , . . . , Vk
and a separator S that partition V such that there are no
edges between the blocks. Again, a balancing constraint
demands |Vi | ≤ (1+)d|V |/ke. However, there is no balancing
constraint on the separator S. The objective is to minimize
the size of the separator |S|. Note that removing the set S
from the graph results in at least k connected components
and that the blocks Vi itself do not need to be connected
components. Two blocks of Vi and Vj are adjoint if there
exists a separator node s ∈ S that connects both blocks.
Note that s can separate more than two blocks. For the
separator case, edges in the quotient graph are induced by
adjoint blocks. By default, our initial inputs will have unit
edge and node weights. However, the results in this paper
are easily transferable to node and edge weighted problems.
A matching M ⊆ E is a set of edges that do not share any
common nodes, i.e. the graph (V, M ) has maximum degree
one. Contracting an edge {u, v} replaces the nodes u and v
by a new node x connected to the former neighbors of u and
v. We set c(x) = c(u) + c(v). If replacing edges of the form
{u, w} , {v, w} would generate two parallel edges {x, w}, we
insert a single edge with ω({x, w}) = ω({u, w}) + ω({v, w}).
Uncontracting an edge e “undoes” its contraction. In order to
avoid tedious notation, G will denote the current state of the
graph before and after a (un)contraction unless we explicitly
want to refer to different states of the graph.
The multilevel approach consists of three main phases. In
the contraction (coarsening) phase, we iteratively identify
matchings M ⊆ E and contract the edges in M . Contraction
should quickly reduce the size of the input and each computed
level should reflect the global structure of the input graph.
Contraction is stopped when the graph is small enough so
that the problem can be solved by some other potentially
more expensive algorithm. In the local search (or uncoarsening) phase, matchings are iteratively uncontracted. After
uncontracting a matching, a local search algorithm moves
nodes to decrease the size of the separator or to to improve

balance of the block while keeping the size of the separator.
The intuition behind the approach is that a good solution at
one level of the hierarchy will also be a good solution on the
next finer level so that local search will quickly find a good
solution.

2.2

Related Work

Here, we focus on results closely related to our main contributions, as well as previous work on the node separator
problem. However, we briefly mention that there has been
a huge amount of research on graph partitioning, which is
closely related to the node separator problem. We refer the
reader to [3, 5] for thorough reviews of the results in this
area.
2-way Node Separators. In contrast to the NP-hardness of
the problem in general, Lipton and Tarjan [19] showed that
small 2-way balanced separators can always be found in linear
time for planar graphs. Their planar separator theorem states
that, for planar graphs, one can always
p find a 2-way separator
S in linear time such that |S| = O( |V |) and |Vi | ≤ 2|V |/3.
Note that, to achieve better balance, the problem remains
NP-hard [11] even for planar graphs.
For general graphs there are several heuristics to compute
small node separators. A common and simple method is
to first compute an edge separator using a multilevel graph
partitioning algorithm, and then compute a node separator
by selecting nodes incident to the edge separator [24, 27]. A
major drawback to this method is that the graph partitioning
objective—to minimize the number of cut edges—differs from
the objective of the node separator problem. This difference
in combinatorial structure, unfortunately, means that graph
partitioning approaches are unlikely to find high quality solutions.
The Metis [16] and Scotch [23] graph partitioners use a
multilevel approach to obtain a 2-way node separator. After
contraction, both tools compute a node separator on the
coarsest graph using a greedy algorithm. This separator is
then transferred level-by-level, dropping non-needed nodes
on each level and applying Fiduccia-Mattheyses (FM) style
local search. LaSalle and Karypis [17] further gave a sharedmemory parallel algorithm and showed that a multilevel
approach combining greedy local search with a segmented
FM algorithm can outperform serial FM algorithms.
Other recent approaches look at variations of the node
separator problem, such as Pareto solutions for edge cut
versus balance [15], and enforcing both upper and lower
bounds on block sizes [14].
k-way Node Separators. In the theoretical algorithms literature, a multiway separator is the generalization of separator
to a higher number of blocks. Frederickson [10] first gave
this generalization, and showed that planar graphs can be
partitioned into O(|V |/k)√subsets of size at most k, where
each subgraph shares O( k) boundary vertices with other
subgraphs. Frederickson’s generalization of a separator is
different than what we consider here: we do not attempt to

Distributed Evolutionary k-way Node Separators
minimize the number of nodes that separate pairs of blocks,
instead we minimize the total number of nodes that collectively separate all blocks. In practice, the balance constraint
on the block size may also implicitly minimize the number
of separator nodes between blocks, but this is not strictly
enforced.
We are currently unaware of any existing algorithm to
compute a k-way node separator. However, we note that,
similar to 2-way node separators, a k-way node separator
may be computed by first computing a k-way edge separator,
and then keeping some or all of the nodes incident to the
edge separator as a node separator.

2.3

Detailed Related Work

Recently, we presented a new multilevel algorithm for the
2-way node separator problem [26]. We outline the details
of the multilevel algorithm here since we modify this algorithm to compute k-way node separators and then use the
modified algorithm to compute the initial population of the
evolutionary algorithm.
During coarsening, they use a two-phase approach, which
makes contraction more systematic by separating two issues:
A rating function and a matching algorithm. Hence, the
coarsening algorithm captures both local information and
the global structure of the graph. While the rating function
allows a flexible characterization of what a “good” contracted
graph is, the simple, standard definition of the matching
problem allows to reuse previously developed algorithms for
weighted matching. Their method further uses the Global
Path Algorithm (GPA) [21] to compute matchings, which
runs in near-linear time. GPA scans the edges in order of decreasing weight (rating) but rather than immediately building
a matching, it first constructs a collection of paths and evenlength cycles. Afterwards, optimal solutions are computed for
each of these paths and cycles using dynamic programming.
Coarsening is stopped as soon as the graph has less than
ten thousand nodes. To compute an initial separator, Sanders
and Schulz compute an edge separator, from which they derive
a node separator. Conversion is done by using all boundary
nodes as initial separator S and using the flow-based technique
described below to select the smallest separator contained in
the induced bipartite subgraph.
Two-way local search is based on localized local search
and flow-based techniques. Localized local search algorithms
for the node separator problem are initialized only with a
subset of given separator instead of the whole separator set.
In each iteration a separator node with the highest priority
not violating the balance constraint is moved. The priority is
based on the gain concept, i.e. the decrease in the objective
when the separator node is moved into a block. More precisely,
the gain of the node is the weight of v minus the weight of
the nodes that have to be added to the separator once it is
moved. Each node is moved at most once out of the separator
within a single local search. After a node is moved, newly
added separator nodes become eligible for movement.

The other local search algorithm contributed is based on
maximum flows. More precisely, the authors solve a nodecapacitated flow problem F = (VF , EF ) to improve a given
node separator. We shortly outline the details. Given a set
of nodes A ⊂ V , its border is defined as ∂A := {u ∈ A |
∃(u, v) ∈ E : v 6∈ A}. The set ∂1 A := ∂A ∩ V1 is called
left border of A and the set ∂2 A := ∂A ∩ V2 is called right
border of A. An A induced flow problem F is the node
induced subgraph G[A] using ∞ as edge-capacities and the
node weights of the graph as node-capacities. Additionally
there are two nodes s, t that are connected to the border of
A. More precisely, s is connected to all left border nodes ∂1 A
and all right border nodes ∂2 A are connected to t. These new
edges get capacity ∞. Note that the additional edges are
directed. F has the balance property if each (s,t)-flow induces
a balanced node separator in G, i.e. the blocks Vi fulfill the
balancing constraint. The basic idea is to construct a flow
problem F having the balance property. Such a subgraph is
found by performing breadth first searches (BFS) initialized
with the separator nodes.
The algorithms starts by setting A to S and extending
it by performing two BFS. The first BFS is initialized with
the current separator nodes S and only looks at nodes in
block V1 . The same is done during the second BFS with
the difference that now looks at nodes of block V2 . Each
node touched by any of the BFS is added to A. The BFSs
are stopped in such a way that the final solution of the flow
problem (which can be transformed into a separator of the
original problem) yields a balanced separator in the original
graph. To obtain even better solutions, larger flow-problems
can be defined by dropping the requirement that each cut in
the flow problem corresponds to a balanced node separator
in the original graph. If the resulting node separator is not
balanced, then the algorithms starts again with a smaller flow
problems, i.e. stopping the BFS to define the flow problem
earlier.
To improve solution quality, the notion of iterated multilevel
schemes has been introduced to the node separator problem.
Here, one transfers a solution of a previous multilevel cycle
down the hierarchy and uses it as initial solution. More
precisely, this can be done by not contracting any cut edge,
i.e. an edge running between a block and the separator. This
is achieved by modifying the matching algorithm to not match
any edge that runs between Vi and S (i = 1, 2, . . . , k). Hence,
when contraction is done, every edge leaving the separator
will remain and one can transfer the node separator down
in the hierarchy. Thus a given node separator can be used
as initial node separator of the coarsest graph (having the
same balance and size as the node separator of the finest
graph). This ensures non-decreasing quality, if the local
search algorithm guarantees no worsening.

3

LOCAL SEARCH AND BALANCING

Local search is used to improve a given solution to the node
separator problem on each level of the multilevel hierarchy.
As the term implies we locally search for a better separator

Peter Sanders, Christian Schulz, Darren Strash, and Robert Williger
around the current separator in order to find a new locally
optimal solution. In this section, we show how we can use
the flow-based local improvement method described above
to locally improve a k-way separator for k > 2 and describe
algorithms that are able to balance solutions, e.g. solutions
that contain blocks with too many vertices. These algorithms
are used to create the initial population of our evolutionary
algorithm as well as to provide the combine and mutation
operations. Our algorithm is called Adv and the evolutionary
algorithm that is introduced later AdvEvo.

3.1

k-way Local Search

Our k-way local search builds on top of the flow-based search
which is intended for improving a separator with k = 2. The
main idea is to find pairs of adjoint blocks and then perform
local search on the subgraph induced by adjoint block pairs.
Preprocessing. In order to find pairs of adjoint blocks, we
look at separator nodes which directly separate two different blocks, meaning these separator nodes are adjacent to
nodes from at least two different blocks not including the
separator. In general directly separating nodes do not have
to exist (see Figure 1). In other words, it may be that a
separator disconnects two blocks, but the shortest path distance between the blocks is greater or equal to two. Using
a preprocessing step, we first make sure that each separator
node is adjacent to at least two blocks, i.e. each separator
node is directly separating.
The preprocessing step works as follows: we iterate over all
separator nodes and try to remove them from the separator
if they do not directly separate two blocks. The order in
which we look at the separator nodes is given by the number of adjacent blocks (highest first). Let s be the current
separator node under consideration. If it has two or more
non-separator neighbors in different blocks, it already directly
separates at least two blocks and we continue. If s only has
neighbors in a single block in addition to the separator, we
move it into that block. Lastly, if s only has other separator
nodes as neighbors, we put it into a block having smallest
overall weight. In each step, we update the priorities of
adjacent neighboring separator nodes. Note that nodes are
only removed from the separator and never added. Moreover,
removing a node from the separator can increase the priority

Figure 1: Illustration of the preprocessing for a
graph with blocks V1 (green), V2 (blue) and separator
S (red).

of an adjacent separator node only by one. As soon as the
priority of a node is larger than one, it is directly separating
and we do not have to look at the vertex again. After the
algorithm is done, each separator node is directly separating
at least two blocks and we can build the quotient graph in
order to find adjoint blocks. Our preprocessing can introduce
imbalance to the solution. Hence, we run the balance routine
defined below after preprocessing.
Pair-wise Local Search. Subsequent to the preprocessing
step, we identify the set of all adjoint block pairs P by
iterating through all separator nodes and their adjacent nodes.
We iterate through all pairs p = (A, B) ∈ P and build the
subgraph Gp . Gp is induced by the set of nodes consisting of all
nodes in A and B as well as all separator nodes that directly
separate the blocks. After building Gp , we run local search
designed for 2-way separators on this subgraph. Note that an
improvement in the separator size between A and B directly
corresponds to an improvement to the overall separator size.
To gain even smaller separators and because the solution
is potentially modified by local search, we repeat local search
multiple times in the following way. The algorithm is organized in rounds. In each round, we iterate over the elements
in P and perform local search on each induced subgraph. If
local search has not been successful, we remove p from P .
Otherwise, we keep p for the next round.

3.2

Balancing

To guarantee the balance constraint, we use a balance operation. Given an imbalanced separator of a graph, the algorithm
returns a balanced node separator. Roughly speaking, we
move nodes from imbalanced blocks towards the blocks that
can take nodes without becoming overloaded (see Figure 2
for an illustrating example). As long as there are imbalanced
blocks, we iteratively repeat the following steps:
First, we find a path p from the heaviest block H to
the lightest block L in the quotient graph. If there is no
such path, we directly move a node to the lightest block
and make its neighbors separator nodes. Next, we iterate
through the edges (A, B) ∈ p and move nodes from A into
B. In general, we move min(Lmax − |L|, |H| − Lmax ) nodes
along the path, i.e. as many nodes as the lightest block can
take without getting overloaded and as little nodes necessary
so that the heaviest block is balanced. Moving nodes is
based on gain of the movement as defined in Section 2.3.
Basically, we use a priority queue of separator nodes that
directly separate A and B with the key being set to the
gain. Note that these movements create new separator nodes
and can potentially worsen solution quality. We use the
gain definition because our primary target is to minimize the
increase of the separator size.
Then we dequeue nodes from the our priority queue until
A is balanced. We move each dequeued node s to B and
move its neighbors being in A into the separator and the
priority queue. Also the priorities of the nodes in the queue
are updated. After moving the nodes A will be balanced. If
B is imbalanced, we continue with the next pair in the path,

Distributed Evolutionary k-way Node Separators

Figure 2: Illustration of the quotient graph and
the balancing path (blue) from an imbalanced block
(red) to the lightest block (green).
i.e. sending the same amount of nodes. If B is also balanced,
we are done with this path and do not move any more nodes.
Our algorithm continues with the next imbalanced block.

4

EVOLUTIONARY K-WAY NODE
SEPARATORS

Our EA starts with a population of individuals (in our case
the node separator of the graph) and evolves the population into different populations over several rounds. In each
round, the EA uses a selection rule based on the fitness of the
individuals (in our case the size of the separator) of the population to select good individuals and combine them to obtain
improved offspring. Note that we can use the size/weight of
the separator as a fitness function since our algorithm always
generates separators fulfilling the given balance constraint,
i.e. there is no need to use a penalty function to ensure that
the final separator is feasible. When an offspring is generated
an eviction rule is used to select a member of the population
and replace it with the new offspring. In general one has to
take both into consideration, the fitness of an individual and
the distance between individuals in the population [1]. Our
algorithm generates only one offspring per generation.

4.1

Combine Operation

We now describe the combine operator. Our combine operator assures that the offspring has an objective at least as good
as the best of both parents. Roughly speaking, the combine operator combines an individual/separator P = V1P , ..., VkP , S P
(which has to fulfill a balance constraint) with a second individual/separator C = V1C , ..., VkC , S C . Let P be the individual
with better fitness.
The algorithm begins with selecting two individuals from
the population. The selection process is based on the tournament selection rule [22], i.e. P is the fittest out of two
random individuals R1 , R2 from the population and the same
is done to select C. Both node separators are used as input
for our multi-level algorithm in the following sense. Let E
be the set of edges that are cut edges, i.e. edges that run
between blocks and the separator, in either P or C. All edges
in E are blocked during the coarsening phase, i.e. they are
not contracted during the coarsening phase. In other words

these edges are not eligible for the matching algorithm used
during the coarsening phase and therefore are not part of
any matching.
The stopping criterion of the multi-level algorithm is modified such that it stops when no contractable edge is left.
As soon as the coarsening phase is stopped, we apply the
separator P to the coarsest graph and use this as initial
separator. This is possible since we did not contract any
edge running between the blocks and the separator in P.
Note that due to the specialized coarsening phase and this
specialized initial phase we obtain a high quality initial solution on a very coarse graph which is usually not discovered
by conventional algorithms that compute an initial solution.
Since our local search algorithms guarantee no worsening
of the input solution and we use random tie breaking we
can assure non-decreasing quality. Note that the local search
algorithms can effectively exchange good parts of the solution
on the coarse levels by moving only a few vertices.
Also note that this combine operator can be extended to
be a multi-point combine operator, i.e. the operator would
use ` instead of two parents. However, during the course
of the algorithm a sequence of two point combine steps is
executed which somehow "emulates" a multi-point combine
step. Therefore, we restrict ourselves to the case ` = 2.
When the offspring is generated we have to decide which
solution should be evicted from the current population. We
evict the solution that is most similar to the offspring among
those individuals in the population that have an objective
worse or equal than the offspring itself. Here, we define
the similarity σ of two node separators S1 and S2 as the
cardinality of the symmetric difference of both separators:
σ = |(S1 \ S2 ) ∪ (S2 \ S1 )|. Therefore σ denotes the number
of nodes contained in one separator but not in the other. This
ensures some diversity in the population and hence makes
the evolutionary algorithm more effective.

4.2

Mutation Operation

The mutation operation works similar to the combine operation. The main difference is that there is only one input
individual to the multi-level algorithm and that the offspring
can be less fit compared to the input individual. Hence, only
edges that run between the blocks and the separator of that
individual are not eligible for the matching algorithm. This
way the input individual can be transferred downwards in
the hierarchy. Additionally, the solution is not used as initial
separator but the initial algorithm is performed to find an
initial separator. Note however due to the way the coarsening
process is defined the input separator is still contained in the
coarsest graph.

5

PUTTING THINGS TOGETHER AND
PARALLELIZATION

We now explain parallelization and describe how everything
is put together to be our full evolutionary algorithm AdvEvo.
We use a parallelization scheme that has been successfully
used in graph partitioning [25]. Each processing element

Peter Sanders, Christian Schulz, Darren Strash, and Robert Williger
(PE) basically performs the same operations using different
random seeds (see Algorithm 1). First we estimate the population size S: each PE creates an individuum and measures
the time t spend. We then choose S such that the time for
creating S node separators is approximately ttotal /f where
the fraction f is a tuning parameter and ttotal is the total
running time that the algorithm is given to produce a node
separator of the graph. Each PE then builds its own population, i.e. our multi-level algorithm is called several times to
create S individuals/separators. Afterwards the algorithm
proceeds in rounds as long as time is left. With corresponding
probabilities, mutation or combine operations are performed
and the new offspring is inserted into the population.
We choose a parallelization/communication protocol that
is quite similar to randomized rumor spreading [9] which
has shown to be scalable in an evolutionary algorithm for
graph partitioning [25]. We follow their description closely.
Let p denote the number of PEs used. A communication
step is organized in rounds. In each round, a PE chooses
a communication partner and sends her the currently best
node separator P of the local population. The selection of
the communication partner is done uniformly at random
among those PEs to which P not already has been send to.
Afterwards, a PE checks if there are incoming individuals
and if so inserts them into the local population using the
eviction strategy described above. If P is improved, all PEs
are again eligible. This is repeated log p times. The algorithm
is implemented completely asynchronously, i.e. there is no
need for a global synchronization.

approach, but keep the rest of the algorithm. More precisely,
this means that the population of the algorithm are still graph
partitions instead of separators, but for example selection is
based on the size of the derivable separator. Additionally,
the combine operations in KaFFPaE still optimize for cuts
instead of separators. This algorithm is called SimpleEvo.

6

EXPERIMENTS

Methodology. We have implemented the algorithm described
above within the KaHIP framework using C++ and compiled all algorithms using gcc 4.8.3 with full optimization’s
turned on (-O3 flag).
We integrated our algorithms in
KaHIP v1.00. Our new codes will also be included into the
KaHIP graph partitioning framework. Each run was made
on a machine that has four Octa-Core Intel Xeon E5-2670
processors running at 2.6 GHz with 64 GB local memory.
Our main objective is the cardinality of node separators on
the input graph. In our experiments, we use the imbalance
parameter  = 3% since this is one of the default values in
the Metis graph partitioning framework. Our full algorithm
is not too sensitive about the precise choice with most of the
parameters. However, we performed a number of experiments
to evaluate the influence and choose the parameters of our
algorithms. We omit details here and refer the reader to [30].
We mark the instances that have been used for the parameter
tuning in Table 1 with a * and exclude these graphs from
our experiments.
We present multiple views on the data: average values (geometric mean) as well as convergence plots that show quality
achieved by the algorithms over time and performance plots.

Algorithm 1 locallyEvolve
estimate population size S
while time left
if elapsed time < ttotal /f then
create individual, insert into local population
else
flip coin c with corresponding probabilities
if c shows head then perform mutation
else perform combine
insert offspring into population if possible
communicate according to comm. protocol

5.1

Miscellaneous

Besides Adv and AdvEvo, we also use two more algorithms
to compare solution quality. The first one is a sequential
algorithm that starts by computing a k-way partition using
KaFFPa-Strong and derives a k-way separator by pair-wise
decoupling by using the method of Pothen and Fan [24] on
each adjacent pair of blocks. The main idea of Pothen and
Fan is to compute a minimum vertex cover in the bipartite
subgraph induced by the set of cut edges between two pairs
of blocks. The union of the computed separators nodes is
a k-way separator. In our experiments, the algorithm is
called Simple. The second algorithm, is a modification of
KaFFPaE [25] which is an evolutionary algorithm to compute
graph partitions. We modify the fitness function to be the
size of the separator that can be derived using the Simple

Graph

n

Walshaw Graphs
add20
2 395
data
2 851
3elt
4 720
uk
4 824
add32
4 960
bcsstk33*
8 738
whitaker3
9 800
crack
10 240
wing_nodal 10 937
fe_4elt2
11 143
vibrobox*
12 328
bcsstk29
13 992
4elt
15 606
fe_sphere
16 386
cti
16 840
memplus
17 758
cs4
22 499
bcsstk30
28 924
bcsstk31
35 588
fe_pwt
36 519

Graph

n

Walshaw Graphs
bcsstk32
44 609
fe_body*
45 087
t60k
60 005
wing
62 032
brack2
62 631
finan512
74 752
fe_tooth*
78 136
fe_rotor
99 617
UF Graphs
cop20k_A
99 843
2cubes_sphere*
101 492
thermomech_TC 102 158
cfd2
123 440
boneS01
127 224
Dubcova3
146 689
bmwcra_1
148 770
G2_circuit*
150 102
c-73
169 422
shipsec5
179 860
cont-300
180 895

Table 1: Walshaw graphs and florida sparse matrix
graphs from [26]. Basic properties of the instances.
Graphs with a * have been used for parameter tuning and are excluded from the evaluation.

2100

k=32
SimReps
SimEvo

1900

AdvReps
AdvEvo

2

10 50
500
normalized time tn

440
410
380

k=16
SimReps
SimEvo

1200

1300

AdvReps
AdvEvo

1100

660

5
50 500 10000
normalized time tn

SimReps
SimEvo

5
50 500 10000
normalized time tn

2

10 50
500 5000
normalized time tn
k=64

3200

SimReps
SimEvo

720

780

AdvReps
AdvEvo

AdvReps
AdvEvo

AdvReps
AdvEvo

SimReps
SimEvo

2900

k=8

k=4

2600

5
50 500 10000
normalized time tn

mean min separator size

SimReps
SimEvo

mean min separator size

AdvReps
AdvEvo

mean min separator size

160 165 170 175

k=2

1700

mean min separator size

mean min separator size

mean min separator size

Distributed Evolutionary k-way Node Separators

2

10 50
500
normalized time tn

Figure 3: Convergence plots for different values of k for different algorithms.

Peter Sanders, Christian Schulz, Darren Strash, and Robert Williger
We now explain how we compute the convergence plots. We
start explaining how we compute them for a single instance I:
whenever a PE creates a separator it reports a pair (t, separator size), where the timestamp t is the currently elapsed time
on the particular PE and separator size refers to the size of
the separator that has been created. When performing multiple repetitions, we report average values (t, avg. separator
size) instead. After the completion of algorithm we are left
with P sequences of pairs (t, separator size) which we now
merge into one sequence. The merged sequence is sorted by
the timestamp t. The resulting sequence is called T I . Since
we are interested in the evolution of the solution quality, we
I
compute another sequence Tmin
. For each entry (in sorted
order) in T I , we insert the entry (t, mint0 ≤t separator size(t0 ))
I
into Tmin
. Here, mint0 ≤t separator size(t0 ) is the minimum
I
separator size that occurred until time t. Nmin
refers to the
normalized sequence, i.e. each entry (t, separator size) in
I
Tmin
is replaced by (tn , separator size) where tn = t/tI and
tI is the average time that the sequential algorithm needs to
compute a separator for the instance I. To obtain average
values over multiple instances we do the following: for each
I
instance we label all entries in Nmin
, i.e. (tn , separator size)
is replaced by (tn , separator size, I). We then merge all
I
sequences Nmin
and sort by tn . The resulting sequence is
called S. The final sequence Sg presents event based geometric averages values. We start by computing the geometric
I
mean value G using the first value of all Nmin
(over I). To
obtain Sg , we basically sweep through S: for each entry (in
sorted order) (tn , c, I) in S, we update G, i.e. the separator
size of I that took part in the computation of G is replaced
by the new value c, and insert (tn , G) into Sg . Note, c can
be only smaller than or equal to the old value of I.
Instances. We use the small and Florida Sparse Matrix
graphs from [26] which are from various sources to test our
algorithm. Small graphs have been obtained from Chris
Walshaw’s benchmark archive [29]. Graphs derived from
sparse matrices have been taken from the Florida Sparse
Matrix Collection [6]. Basic properties of the instances can
be found in Table 1.

6.1

Separator Quality

In this section we compare our algorithms in a setting where
each one gets the same (fairly large) amount of time to
compute a separator. We do this on the graphs from our
benchmark set. We use all 16 cores per run of our machine
(basically one node of the cluster) and two hours of time
per instance when we use the evolutionary algorithm to
create separators. We parallelized repeated executions of
the sequential algorithms (embarrassingly parallel, different
seeds) and also gave them 16 PEs and two hours of time
to compute a separator. We look at k ∈ {2, 4, 8, 16, 32, 64}
and performed three repetitions per instance. To see how
the solution quality of the different algorithms evolves over
time, we use convergence plots. Figure 3 shows convergence
plots for k ∈ {2, 4, 8, 16, 32, 64}. Additionally, Tables 2 and

k
2
4
8
16
32
64
overall

AdvEvo
159.4
373.9
664.4
1097.9
1694.2
2601.8
+0%

AdvReps
0.0
+1.7%
+2.7%
+5.1%
+6.8%
+8.1%
4.1%

SimEvo
+3.8%
+5.6%
+8.4%
+10.4%
+11.8%
+15.3%
9.2%

SimReps
+5.0%
+7.7%
+11.1%
+13.4%
+14.4%
+17.8%
11.6%

Table 2: Average of AdvEvo and average increase in
separator size for different algorithms.
Algorithm
AdvEvo
AdvReps
SimEvo
SimReps

#≤
181
65
33
29

#<
122
7
3
0

Table 3: Number of instances where algorithm X is
best w.r.t to ≤ and <. The total number of instances
is 192.
3 summarize final results. Tables in the Appendix present
detailed per instance results.
First of all, the improvements of the evolutionary algorithms relative to repeated executions increase with growing
k. This is due to the fact that the problems become more difficult when increasing the number of blocks k. For larger values
of k, the quality gap between the evolutionary algorithm AdvEvo and SimEvo as well as the other algorithms increases
with more time invested. On the other hand, for k = 2 there
is almost no difference between the results produced by the
evolutionary algorithm AdvEvo and the non-evolutionary
version AdvReps. Overall, the experimental data indicates
the AdvEvo is the best algorithm. Separators produced by
AdvEvo are 4.1%, 9.2% and 11.6% smaller compared to AdvReps, SimEvo, and SimReps on average. Additionally, our
advanced evolutionary algorithm computes the best result
on 181 out of 192 instances.
Note that single executions of the simple algorithms are
much faster. However, the results of our experiments performed in this section emphasize that one cannot simply use
the best result out of multiple repetitions of a faster algorithm
to obtain the same solution quality. Yet it is interesting to
see that SimpleEvo, where only the fitness function of the
evolutionary algorithm is modified and the combine operation
still optimizes for edge cuts of partitions, computes better
solutions than its non-evolutionary counter part SimReps.

7

CONCLUSION

In this work, we derived a new approach to find small node
separators in large graphs which combines an evolutionary
search algorithm with a multilevel method. We combined
these techniques with a scalable communication protocol
and obtain a system that is able to compute high quality
solutions in a short amount of time. Experiments show that
our advanced evolutionary algorithm computes the best result
on 94% of the benchmark instances. In future work, we aim
to look at different types of applications, in particular those
applications in which the running time may not be considered

Distributed Evolutionary k-way Node Separators
a drawback when the node separator has the highest quality.
Acknowledgements. The authors acknowledge support by
the state of Baden-Württemberg through bwHPC.

REFERENCES
[1] T. Bäck. 1996. Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic
Algorithms. Ph.D. Dissertation.
[2] S. N. Bhatt and F. T. Leighton. 1984. A framework for solving
VLSI graph layout problems. J. Comput. System Sci. 28, 2 (1984),
300 – 343. DOI:http://dx.doi.org/10.1016/0022-0000(84)90071-0
[3] C. Bichot and P. Siarry (Eds.). 2011. Graph Partitioning. Wiley.
[4] T. N. Bui and C. Jones. 1992. Finding Good Approximate Vertex
and Edge Partitions is NP-hard. Inform. Process. Lett. 42, 3
(1992), 153–159.
[5] A. Buluç, H. Meyerhenke, I. Safro, P. Sanders, and C. Schulz.
2016. Recent Advances in Graph Partitioning. In Algorithm
Engineering – Selected Results (LNCS), Vol. 9920. Springer,
117–158.
[6] T. Davis. 2017. The University of Florida Sparse Matrix Collection. (2017).
[7] D. Delling, M. Holzer, K. Müller, F. Schulz, and D. Wagner.
2009. High-performance multi-level routing. The Shortest Path
Problem: Ninth DIMACS Implementation Challenge 74 (2009),
73–92.
[8] J. Dibbelt, B. Strasser, and D. Wagner. 2014. Customizable
contraction hierarchies. In 13th Int. Symp. on Exp. Algorithms
(SEA’14). Springer, 271–282.
[9] B. Doerr and M. Fouz. 2011. Asymptotically Optimal Randomized Rumor Spreading. In Proceedings of the 38th International
Colloquium on Automata, Languages and Programming, Proceedings, Part II (LNCS), Vol. 6756. Springer, 502–513.
[10] G. N. Federickson. 1987. Fast Algorithms for Shortest Paths
in Planar Graphs, with Applications. SIAM J. Comput. 16,
6 (1987), 1004–1022. DOI:http://dx.doi.org/10.1137/0216064
arXiv:http://dx.doi.org/10.1137/0216064
[11] J. Fukuyama. 2006. NP-Completeness of the Planar Separator
Problems. Journal of Graph Algorithms and Applications 10, 2
(2006), 317–328.
[12] M. R. Garey and D. S. Johnson. 2002. Computers and Intractability. Vol. 29. WH Freeman & Co., San Francisco.
[13] A. George. 1973. Nested Dissection of a Regular Finite Element
Mesh. SIAM J. Numer. Anal. 10, 2 (1973), 345–363.
[14] W. W. Hager, J. T. Hungerford, and I. Safro. 2014. A Multilevel Bilinear Programming Algorithm For the Vertex Separator
Problem. Technical Report.
[15] M. Hamann and B. Strasser. 2016. Graph Bisection with ParetoOptimization. In Proc. of the Eighteenth Workshop on Algorithm
Engineering and Experiments, ALENEX’16. SIAM, 90–102. DOI:
http://dx.doi.org/10.1137/1.9781611974317.8
[16] G. Karypis and V. Kumar. 1998. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM Journal
on Scientific Computing 20, 1 (1998), 359–392.
[17] D. LaSalle and G. Karypis. 2015. Efficient Nested Dissection for
Multicore Architectures. In Euro-Par 2015: Parallel Processing.
Springer, 467–478.
[18] C. E. Leiserson. 1980. Area-Efficient Graph Layouts. In 21st
Symposium on Foundations of Computer Science. IEEE, 270–
281.
[19] R. J. Lipton and R. E. Tarjan. 1979. A Separator Theorem for
Planar Graphs. SIAM J. Appl. Math. 36, 2 (1979), 177–189.
[20] R. J. Lipton and R. E. Tarjan. 1980. Applications of a Planar
Separator Theorem. SIAM Journal On Computing 9, 3 (1980),
615–627.
[21] J. Maue and P. Sanders. 2007. Engineering Algorithms for
Approximate Weighted Matching. In Proceedings of the 6th
Workshop on Experimental Algorithms (WEA’07) (LNCS),
Vol. 4525. Springer, 242–255.
http://dx.doi.org/10.1007/
978-3-540-72845-0_19
[22] B. L Miller and D. E Goldberg. 1996. Genetic Algorithms, Tournament Selection, and the Effects of Noise. Evolutionary Computation 4, 2 (1996), 113–131.
[23] F. Pellegrini. 2017. Scotch Home Page. (2017). http://www.labri.
fr/pelegrin/scotch.
[24] A. Pothen, H. D. Simon, and K. P. Liou. 1990. Partitioning
Sparse Matrices with Eigenvectors of Graphs. SIAM J. Matrix

Anal. Appl. 11, 3 (1990), 430–452.
[25] P. Sanders and C. Schulz. 2012. Distributed Evolutionary Graph
Partitioning. In Proc. of the 12th Workshop on Algorithm Engineering and Experimentation (ALENEX’12). 16–29.
[26] P. Sanders and C. Schulz. 2016. Advanced Multilevel Node Separator Algorithms. In 15th International Symposium on Experimental Algorithms, SEA 2016, Vol. 9685. Springer, 294–309.
[27] C. Schulz. 2013. High Quality Graph Partititioning. Ph.D.
Dissertation. Karlsruhe Institute of Technology.
[28] F. Schulz, D. Wagner, and C. Zaroliagis. 2002. Using multi-level
graphs for timetable information in railway systems. In Proceedings of Algorithm Engineering and Experiments (ALENEX).
Springer, 43–59.
[29] A. J. Soper, C. Walshaw, and M. Cross. 2004. A Combined
Evolutionary Search and Multilevel Optimisation Approach to
Graph-Partitioning. Journal of Global Optimization 29, 2 (2004),
225–241.
[30] R. Williger. 2016. Evolutionary k-way Node Separators. Bachelor’s Thesis. Karlsruhe Institute of Technologie.

Peter Sanders, Christian Schulz, Darren Strash, and Robert Williger
graph
3elt
3elt
3elt
3elt
3elt
3elt
4elt
4elt
4elt
4elt
4elt
4elt
add20
add20
add20
add20
add20
add20
add32
add32
add32
add32
add32
add32
bcsstk29
bcsstk29
bcsstk29
bcsstk29
bcsstk29
bcsstk29
bcsstk30
bcsstk30
bcsstk30
bcsstk30
bcsstk30
bcsstk30
bcsstk31
bcsstk31
bcsstk31
bcsstk31
bcsstk31
bcsstk31
bcsstk32
bcsstk32
bcsstk32
bcsstk32
bcsstk32
bcsstk32
bmwcra_1
bmwcra_1
bmwcra_1
bmwcra_1
bmwcra_1
bmwcra_1

k
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64

AdvEvo
AdvReps
SimpleEvo
min
avg
min
avg
min
avg
43
43
43
43
43
43
97
97
97
97
97
97
158
158
159
159
159
159
269
269
270
270
271
271
452
452
455
456
458
459
706
710
720
721
733
734
68
68
68
68
68
68
157
157
157
157
157
157
253
253
254
254
256
256
438
439
443
445
443
445
737
743
755
757
744
746
1 221
1 227
1 257
1 259
1 234
1 238
26
26
25
25
28
28
37
37
37
37
45
47
67
67
69
70
82
86
95
96
106
108
116
119
110
111
140
140
166
169
138
138
161
164
219
225
2
2
2
2
2
2
6
6
6
6
6
6
11
11
11
11
12
12
20
20
20
20
20
20
33
33
33
33
33
33
114
115
118
119
127
128
180
180
180
180
180
180
528
528
528
528
534
536
948
954
966
968
1 173
1 202
1 512
1 530
1 578
1 578
2 120
2 127
2 231
2 250
2 316
2 326
2 891
2 898
3 130
3 157
3 361
3 371
4 073
4 089
206
206
206
206
206
206
549
549
549
549
573
573
1 121
1 121
1 123
1 123
1 138
1 145
2 128
2 146
2 183
2 201
2 446
2 455
3 195
3 249
3 321
3 338
3 985
3 987
4 709
4 836
5 045
5 111
5 846
5 940
308
308
308
308
317
321
767
767
767
767
802
803
1 433
1 434
1 441
1 442
1 529
1 538
2 353
2 399
2 437
2 446
2 592
2 630
3 635
3 695
3 837
3 874
4 338
4 361
5 102
5 167
5 323
5 394
6 090
6 136
297
297
297
297
322
328
569
569
569
569
633
637
1 145
1 152
1 177
1 183
1 312
1 336
2 080
2 102
2 122
2 131
2 391
2 434
3 422
3 449
3 498
3 524
4 102
4 118
5 386
5 469
5 621
5 677
6 293
6 321
657
657
657
657
684
684
1 668
1 673
1 656
1 659
1 683
1 685
3 918
3 970
4 002
4 013
4 080
4 126
10 011 10 037
9 846
9 921 10 099 10 199
16 089 16 300 16 798 16 979 16 863 16 947
23 586 24 279 25 707 25 809 24 979 25 087
Table 4: Detailed per instance results.

SimpleReps
min
avg
43
43
97
97
160
160
272
272
466
466
746
747
68
68
157
157
254
255
442
444
749
750
1 253
1 253
28
28
49
49
94
94
133
133
170
174
218
221
2
2
6
6
12
12
20
20
33
33
131
131
180
180
534
534
1 086
1 094
2 019
2 062
2 892
2 899
4 065
4 096
206
206
573
573
1 138
1 140
2 430
2 452
3 956
4 008
5 994
6 013
317
319
798
800
1 534
1 545
2 624
2 633
4 361
4 376
6 169
6 205
321
321
627
627
1 315
1 326
2 443
2 468
4 114
4 142
6 348
6 412
683
683
1 659
1 666
4 112
4 133
10 190 10 250
16 725 16 775
24 885 25 042

Distributed Evolutionary k-way Node Separators
graph
boneS01
boneS01
boneS01
boneS01
boneS01
boneS01
brack2
brack2
brack2
brack2
brack2
brack2
cfd2
cfd2
cfd2
cfd2
cfd2
cfd2
cont-300
cont-300
cont-300
cont-300
cont-300
cont-300
cop20k_A
cop20k_A
cop20k_A
cop20k_A
cop20k_A
cop20k_A
crack
crack
crack
crack
crack
crack
cs4
cs4
cs4
cs4
cs4
cs4
cti
cti
cti
cti
cti
cti
data
data
data
data
data
data

k
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64

AdvEvo
AdvReps
SimpleEvo
min
avg
min
avg
min
avg
1 524
1 524
1 524
1 524
1 563
1 563
3 357
3 357
3 357
3 357
3 465
3 469
5 112
5 128
5 139
5 148
5 316
5 351
7 728
7 781
7 776
7 826
8 139
8 179
11 082 11 127 11 400 11 440 11 619 11 670
15 264 15 271 16 495 16 683 16 173 16 219
183
183
183
183
206
208
796
796
796
796
829
831
1 740
1 741
1 759
1 761
1 896
1 899
2 794
2 806
2 868
2 874
3 108
3 119
4 160
4 184
4 282
4 289
4 632
4 647
6 053
6 084
6 361
6 381
6 808
6 841
1 030
1 030
1 030
1 030
1 036
1 036
2 543
2 546
2 548
2 551
2 684
2 688
4 304
4 313
4 304
4 312
4 569
4 581
7 068
7 095
7 018
7 036
7 416
7 440
10 723 10 873 11 165 11 272 12 066 12 088
16 521 17 138 17 829 18 021 18 093 18 179
598
598
598
598
598
598
1 041
1 042
1 063
1 065
1 184
1 184
1 786
1 814
1 807
1 825
2 188
2 192
2 863
2 874
2 893
2 916
3 526
3 528
4 299
4 340
4 413
4 450
5 466
5 483
6 452
6 474
6 667
6 679
8 094
8 105
620
620
620
620
620
620
1 673
1 675
1 676
1 676
1 733
1 741
2 919
2 934
2 939
2 942
2 997
2 999
4 721
4 744
4 765
4 780
4 842
4 864
7 241
7 333
7 525
7 645
7 481
7 502
10 757 10 837 11 721 12 107 11 135 11 147
73
73
73
73
75
75
145
145
145
145
152
152
257
257
258
258
280
282
420
420
421
422
461
465
636
639
648
648
722
724
939
943
958
959
1 098
1 100
287
287
287
287
319
319
727
729
738
740
824
825
1 108
1 109
1 133
1 134
1 244
1 245
1 548
1 558
1 623
1 630
1 812
1 818
2 132
2 148
2 273
2 286
2 512
2 516
2 864
2 909
3 179
3 202
3 433
3 435
266
266
266
266
266
266
756
758
761
761
808
808
1 243
1 270
1 311
1 315
1 537
1 539
1 821
1 845
1 897
1 925
2 287
2 298
2 426
2 457
2 646
2 647
3 257
3 267
3 234
3 242
3 581
3 596
4 489
4 491
51
51
51
51
51
51
96
96
96
96
96
96
165
165
165
165
172
172
275
275
276
276
298
301
448
450
454
454
489
492
688
690
695
697
757
760
Table 5: Detailed per instance results.

SimpleReps
min
avg
1 563
1 565
3 471
3 477
5 358
5 371
8 142
8 189
11 758 11 770
16 296 16 314
205
205
829
829
1 906
1 910
3 117
3 120
4 646
4 651
6 809
6 820
1 036
1 036
2 645
2 667
4 551
4 591
7 374
7 392
11 924 11 956
18 014 18 067
598
598
1 184
1 184
2 188
2 194
3 534
3 537
5 504
5 506
8 168
8 170
620
620
1 716
1 724
2 993
2 996
4 849
4 858
7 423
7 465
11 102 11 155
74
74
152
152
285
286
474
474
735
738
1 123
1 124
322
322
832
836
1 267
1 267
1 827
1 830
2 537
2 541
3 461
3 463
266
266
807
807
1 539
1 539
2 319
2 324
3 258
3 267
4 481
4 491
51
51
97
97
173
173
300
300
499
502
764
764

Peter Sanders, Christian Schulz, Darren Strash, and Robert Williger
graph
Dubcova3
Dubcova3
Dubcova3
Dubcova3
Dubcova3
Dubcova3
fe_4elt2
fe_4elt2
fe_4elt2
fe_4elt2
fe_4elt2
fe_4elt2
fe_pwt
fe_pwt
fe_pwt
fe_pwt
fe_pwt
fe_pwt
fe_rotor
fe_rotor
fe_rotor
fe_rotor
fe_rotor
fe_rotor
fe_sphere
fe_sphere
fe_sphere
fe_sphere
fe_sphere
fe_sphere
finan512
finan512
finan512
finan512
finan512
finan512
memplus
memplus
memplus
memplus
memplus
memplus
shipsec5
shipsec5
shipsec5
shipsec5
shipsec5
shipsec5
t60k
t60k
t60k
t60k
t60k
t60k

k
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64
2
4
8
16
32
64

AdvEvo
AdvReps
SimpleEvo
min
avg
min
avg
min
avg
383
383
383
383
383
383
765
765
765
765
765
765
1 433
1 437
1 436
1 437
1 463
1 475
2 295
2 309
2 319
2 322
2 373
2 398
3 581
3 621
3 707
3 711
3 887
3 893
5 448
5 492
5 706
5 732
5 754
5 772
66
66
66
66
66
66
163
163
162
162
168
169
283
285
288
288
290
291
478
479
482
483
482
484
759
762
780
781
773
774
1 149
1 153
1 185
1 190
1 189
1 191
116
116
116
116
116
116
236
236
236
236
236
236
473
473
473
473
474
474
925
925
929
929
930
930
1 834
1 839
1 909
1 910
1 862
1 864
2 846
2 919
3 025
3 043
3 458
3 472
460
460
460
460
464
464
1 540
1 545
1 543
1 554
1 575
1 593
2 833
2 838
2 844
2 848
2 891
2 891
4 404
4 448
4 483
4 489
4 605
4 632
6 809
6 898
6 943
7 013
7 024
7 065
10 196 10 289 10 534 10 615 10 249 10 293
192
192
192
192
192
192
379
379
380
380
380
380
570
570
575
577
570
570
804
804
852
854
835
835
1 177
1 184
1 262
1 264
1 208
1 213
1 657
1 667
1 803
1 805
1 722
1 723
50
50
50
50
50
50
100
100
100
100
100
100
200
200
200
200
200
200
400
400
400
400
400
400
800
800
800
800
800
800
3 210
3 216
3 259
3 263
3 200
3 200
70
70
70
70
90
103
90
90
91
91
127
131
106
106
106
106
154
158
132
132
151
153
234
240
178
179
194
195
265
268
181
182
205
206
392
412
1 203
1 203
1 203
1 203
1 227
1 231
3 681
3 681
3 681
3 681
3 783
3 793
6 078
6 112
6 198
6 216
6 486
6 509
8 826
8 881
8 850
8 903
9 612
9 650
12 861 12 983 13 521 13 601 14 208 14 236
17 304 17 398 18 114 18 301 21 482 21 594
70
70
70
70
71
71
202
202
202
202
203
203
447
447
449
449
448
448
800
803
807
810
792
793
1 330
1 331
1 339
1 343
1 307
1 308
2 040
2 042
2 104
2 114
2 031
2 043
Table 6: Detailed per instance results.

SimpleReps
min
avg
383
383
765
765
1 463
1 464
2 346
2 355
3 821
3 856
5 763
5 766
66
66
167
167
293
293
486
487
783
785
1 206
1 208
116
116
236
236
476
476
929
929
1 872
1 873
3 447
3 462
464
464
1 573
1 580
2 898
2 899
4 550
4 589
7 037
7 062
10 242 10 261
192
192
380
380
570
570
839
839
1 216
1 218
1 745
1 750
50
50
100
100
200
200
400
400
800
800
3 200
3 200
107
107
123
126
142
144
239
242
264
268
428
436
1 227
1 233
3 801
3 803
6 531
6 549
9 570
9 651
14 316 14 340
21 549 21 611
71
71
203
203
448
448
802
804
1 335
1 336
2 098
2 103

Distributed Evolutionary k-way Node Separators
graph
thermomech_TC
thermomech_TC
thermomech_TC
thermomech_TC
thermomech_TC
thermomech_TC
uk
uk
uk
uk
uk
uk
whitaker3
whitaker3
whitaker3
whitaker3
whitaker3
whitaker3
wing
wing
wing
wing
wing
wing
wing_nodal
wing_nodal
wing_nodal
wing_nodal
wing_nodal
wing_nodal

k

AdvEvo
AdvReps
min
avg
min
avg
2
128
128
128
128
4
390
390
389
389
8
837
839
838
838
16 1 439 1 440 1 447 1 450
32 2 316 2 323 2 345 2 349
64 3 620 3 627 3 672 3 680
2
18
18
18
18
4
37
37
37
37
8
73
73
73
73
16
133
133
134
134
32
223
224
225
226
64
360
362
364
366
2
63
63
63
63
4
186
186
187
187
8
320
320
321
321
16
526
528
531
531
32
803
803
811
811
64 1 183 1 185 1 198 1 199
2
626
626
628
628
4 1 288 1 290 1 296 1 297
8 1 943 1 949 1 977 1 980
16 2 963 2 995 3 085 3 095
32 4 300 4 315 4 492 4 513
64 5 736 5 778 6 267 6 287
2
410
410
410
410
4
811
814
836
837
8 1 177 1 184 1 211 1 216
16 1 793 1 800 1 841 1 850
32 2 494 2 500 2 602 2 625
64 3 243 3 252 3 460 3 467
Table 7: Detailed per instance

SimpleEvo
min
avg
129
129
394
394
843
844
1 445 1 447
2 340 2 347
3 636 3 645
18
18
38
38
77
77
136
136
233
236
387
388
63
63
189
189
321
321
531
532
812
813
1 213 1 216
700
702
1 432 1 433
2 157 2 170
3 378 3 388
4 906 4 917
6 622 6 644
415
415
858
859
1 286 1 287
1 965 1 974
2 791 2 800
3 683 3 685
results.

SimpleReps
min
avg
129
129
394
394
848
848
1 453 1 456
2 345 2 353
3 659 3 663
18
18
38
38
76
76
137
138
240
241
402
403
63
63
189
189
322
322
535
536
821
822
1 233 1 233
704
704
1 453 1 456
2 191 2 191
3 398 3 405
4 911 4 921
6 673 6 677
415
415
863
864
1 294 1 294
1 985 1 987
2 806 2 807
3 696 3 702

