Correlation Clustering with Vertex Splitting
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909299475742720 |
|---|---|
| author | Bentert, Matthias Crane, Alex Drange, Pål Grønås Reidl, Felix Sullivan, Blair D. |
| author_facet | Bentert, Matthias Crane, Alex Drange, Pål Grønås Reidl, Felix Sullivan, Blair D. |
| contents | 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-ε}$-approximation is NP-hard for any constant $ε> 0$. Additionally, we extend the established link between Correlation Clustering and Multicut to the setting with permissive vertex splitting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_10335 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Correlation Clustering with Vertex Splitting Bentert, Matthias Crane, Alex Drange, Pål Grønås Reidl, Felix Sullivan, Blair D. Data Structures and Algorithms Social and Information Networks 05C85 F.2.2; I.5.3 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-ε}$-approximation is NP-hard for any constant $ε> 0$. Additionally, we extend the established link between Correlation Clustering and Multicut to the setting with permissive vertex splitting. |
| title | Correlation Clustering with Vertex Splitting |
| topic | Data Structures and Algorithms Social and Information Networks 05C85 F.2.2; I.5.3 |
| url | https://arxiv.org/abs/2402.10335 |