Correlation Clustering with Vertex Splitting
<|reference_start|>Correlation Clustering with Vertex Splitting: 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-\epsilon}$-approximation is NP-hard for any constant $\epsilon > 0$. Additionally, we extend the established link between Correlation Clustering and Multicut to the setting with permissive vertex splitting.<|reference_end|>
@article{bentert2024correlation,
    title={Correlation Clustering with Vertex Splitting},
    author={Matthias Bentert, Alex Crane, P{aa}l Gr{o}n{aa}s Drange, Felix
  Reidl, Blair D. Sullivan},
    journal={arXiv preprint arXiv:2402.10335},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.10335},
    primaryClass={cs.DS cs.SI}
}