A Parallel 2k Kernel for the Cluster Editing Problem

Abstract

The Cluster Editing problem asks us to edit a graph and turn it into a disjoint union of cliques. We are allowed to both add and remove any edges from the graph to achieve this. The goal is to make as few edits as possible. We will present a parallel version of a 2k Cluster Editing kernel by Cheng and Meng. Our parallel version will use O(n log n) parallel time and O(mn) work. We will show that the rules of the kernel can be applied in parallel without conflicts. Unfortunately this does not guarantee that we apply the rules a constant number of times. There exist certain graphs that still require us to apply the rules a linear number of times. We also provide an implementation of the parallel kernel on a GPU. Our implementation can reduce graphs with a few million edges in just a few seconds. We will show that the rules are applied a constant number of times in practice. One feature of our implementation is that after each rule application we will use the same amount of memory or less, even when we add edges to the graph.