A PTAS for the Cluster Editing Problem on Planar Graphs

摘要

The goal of the cluster editing problem is to add or delete a minimum number of edges from a given graph, so that the resulting graph becomes a union of disjoint cliques. The cluster editing problem is closely related to correlation clustering and has applications, e.g. in image segmentation. For general graphs this problem is APX-hard. In this paper we present an efficient polynomial time approximation scheme for the cluster editing problem on graphs embeddable in the plane with a few edge crossings. The running time of the algorithm is 2~(O(∈ ~(-1)log (∈~(-1))))n for planar graphs and 2~(O(k~2∈~(-1) log(k2∈~(-1))))n for planar graphs with at most k crossings.