The complexity of cluster vertex splitting and company

Abstract

Clustering a graph when the clusters can overlap can be seen from three different angles: We may look for cliques that cover the edges of the graph with bounded overlap, we may look to add or delete few edges to uncover the cluster structure, or we may split vertices to separate the clusters from each other. Splitting a vertex v means to remove it and to add two new copies of v and to make each previous neighbor of v adjacent with at least one of the copies. In this work, we study underlying computational problems regarding the three angles to overlapping clusterings, in particular when the overlap is small. We show that the above-mentioned covering problem is NP-complete. We then make structural observations that show that the covering viewpoint and the vertex-splitting viewpoint are equivalent, yielding NP-hardness for the vertex-splitting problem. On the positive side, we show that splitting at most k vertices to obtain a cluster graph has a problem kernel with O(k) vertices. Finally, we observe that combining our hardness results with structural observations and a so-called critical-clique lemma yields a simple alternative NP-hardness proof for the CLUSTER EDITING WITH VERTEX SPLITTING problem, where we add or delete edges and split vertices to obtain a cluster graph.