2026-07-23T06:31:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20048 2024-05-31T13:11:10Z ddc:004 open_access

Correlation Clustering with Vertex Splitting Bentert, Matthias Crane, Alex Drange, Pål Grønås Reidl, Felix Sullivan, Blair D. graph modification cluster editing overlapping clustering approximation parameterized complexity 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 terms of 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 7-approximation. In the case of CORRELATION CLUSTERING, we establish para-NP-hardness when parameterized by the solution size and demonstrate that computing an n^{1-ε}-approximation is NP-hard for any constant ε > 0. Additionally, we extend an established link between CORRELATION CLUSTERING and MULTICUT to the setting with permissive vertex splits. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthias Bentert and Alex Crane and Pål Grønås Drange and Felix Reidl and Blair D. Sullivan 2024 Is Part Of LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2024.8 urn:nbn:de:0030-drops-200483 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.8 eng https://creativecommons.org/licenses/by/4.0/legalcode