Correlation Clustering with Vertex Splitting

Abstract

We explore Cluster Editing and its generalization Correlation Clustering with a new operation called permissive vertex splitting which addresses finding overlapping clusters in the face of uncertain information. We determine that both problems are NP-hard, yet they exhibit significant differences in parameterized complexity and approximability. For Cluster Editing with Permissive Vertex Splitting, we show a polynomial kernel when parameterized by the solution size and develop a polynomial-time algorithm with approximation factor 7. In the case of Correlation Clustering, we establish para-NP-hardness when parameterized by solution size and demonstrate that computing an $n^{1-\hat{I}\mu }$-approximation is NP-hard for any constant $\hat{I}\mu >0$. Additionally, we extend the established link between Correlation Clustering and Multicut to the setting with permissive vertex splitting.

Version 2 includes minor changes incorporating reviewer feedback. Short version appeared at SWAT 2024