Distributed Evolutionary k-way Node Separators
This work addresses the need for efficient node separators in applications like divide-and-conquer algorithms and VLSI design, offering a scalable solution with incremental improvements.
The paper tackles the problem of computing high-quality k-way node separators in large graphs, presenting a distributed evolutionary algorithm that achieves the best result on 94% of benchmark instances.
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.