DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2024.8

Correlation Clustering with Vertex Splitting

Authors: Matthias Bentert, Alex Crane, Pål Grønås Drange, Felix Reidl, and Blair D. Sullivan

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

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 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.

Cite as

Matthias Bentert, Alex Crane, Pål Grønås Drange, Felix Reidl, and Blair D. Sullivan. Correlation Clustering with Vertex Splitting. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.SWAT.2024.8,
  author =	{Bentert, Matthias and Crane, Alex and Drange, P\r{a}l Gr{\o}n\r{a}s and Reidl, Felix and Sullivan, Blair D.},
  title =	{{Correlation Clustering with Vertex Splitting}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.8},
  URN =		{urn:nbn:de:0030-drops-200483},
  doi =		{10.4230/LIPIcs.SWAT.2024.8},
  annote =	{Keywords: graph modification, cluster editing, overlapping clustering, approximation, parameterized complexity}
}

Search Results

Documents authored by Crane, Alex

Correlation Clustering with Vertex Splitting

Abstract

Cite as

Thanks for your feedback!

Could not send message