On the Complexity of 2-club Cluster Editing with Vertex Splitting
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918045804396544 |
|---|---|
| author | Abu-Khzam, Faisal N. Davot, Tom Isenmann, Lucas Thoumi, Sergio |
| author_facet | Abu-Khzam, Faisal N. Davot, Tom Isenmann, Lucas Thoumi, Sergio |
| contents | Editing a graph to obtain a disjoint union of s-clubs is one of the models for correlation clustering, which seeks a partition of the vertex set of a graph so that elements of each resulting set are close enough according to some given criterion. For example, in the case of editing into s-clubs, the criterion is proximity since any pair of vertices (in an s-club) are within a distance of s from each other. In this work we consider the vertex splitting operation, which allows a vertex to belong to more than one cluster. This operation was studied as one of the parameters associated with the Cluster Editing problem. We study the complexity and parameterized complexity of the s-Club Cluster Edge Deletion with Vertex Splitting and s-Club Cluster Vertex Splitting problems. Both problems are shown to be NP-Complete and APX-hard. On the positive side, we show that both problems are Fixed-Parameter Tractable with respect to the number of allowed editing operations and that s-Club Cluster Vertex Splitting is solvable in polynomial-time on the class of forests. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_04846 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Complexity of 2-club Cluster Editing with Vertex Splitting Abu-Khzam, Faisal N. Davot, Tom Isenmann, Lucas Thoumi, Sergio Data Structures and Algorithms Computational Complexity Editing a graph to obtain a disjoint union of s-clubs is one of the models for correlation clustering, which seeks a partition of the vertex set of a graph so that elements of each resulting set are close enough according to some given criterion. For example, in the case of editing into s-clubs, the criterion is proximity since any pair of vertices (in an s-club) are within a distance of s from each other. In this work we consider the vertex splitting operation, which allows a vertex to belong to more than one cluster. This operation was studied as one of the parameters associated with the Cluster Editing problem. We study the complexity and parameterized complexity of the s-Club Cluster Edge Deletion with Vertex Splitting and s-Club Cluster Vertex Splitting problems. Both problems are shown to be NP-Complete and APX-hard. On the positive side, we show that both problems are Fixed-Parameter Tractable with respect to the number of allowed editing operations and that s-Club Cluster Vertex Splitting is solvable in polynomial-time on the class of forests. |
| title | On the Complexity of 2-club Cluster Editing with Vertex Splitting |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2411.04846 |