An overview of different kernelization algorithms for the cluster editing problem

Abstract

In the cluster editing problem, we try to transform a given graph G into a disjoint union of cliques using less than k edge modifications. In this paper we will focus on the kernelization of the input (G; k). Kernelization is a pre-processing step in which the size of a given input (G; k) is reduced to a kernel (G'; k' ) with |G'| < |G| and k' < k. After the kernelization, the kernel is processed by the normal algorithm, and the optimal solution should be the same as (or easy to find from) the optimal solution of the original problem. In this paper we will give an overview of di erent kernelization algorithms for the cluster editing problem.