  Computing high quality node separators in large graphs is necessary for a
variety of applications, ranging from divide-and-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.
