Correlation Clustering with Vertex Splitting Article Swipe

View

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

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2402.10335

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.

Related Topics

Vertex (Graph Theory)

Concepts

Vertex (graph theory) Cluster analysis Correlation Combinatorics Mathematics Statistics Graph Geometry

Metadata

Type: preprint
Language: en
Landing Page: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.8
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4391940651

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4391940651

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2402.10335

Digital Object Identifier
Title: Correlation Clustering with Vertex Splitting

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-02-15

Full publication date if available
Authors: Matthias Bentert, Alex Crane, Pål Grønås Drange, Felix Reidl, Blair D. Sullivan

List of authors in order
Landing page: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.8

Publisher landing page
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.8

Direct OA link when available
Concepts: Vertex (graph theory), Cluster analysis, Correlation, Combinatorics, Mathematics, Statistics, Graph, Geometry

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4391940651
doi	https://doi.org/10.48550/arxiv.2402.10335
ids.doi	https://doi.org/10.48550/arxiv.2402.10335
ids.openalex	https://openalex.org/W4391940651
fwci
type	preprint
title	Correlation Clustering with Vertex Splitting
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10637
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9240000247955322
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1702
topics[0].subfield.display_name	Artificial Intelligence
topics[0].display_name	Advanced Clustering Algorithms Research
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C80899671
concepts[0].level	3
concepts[0].score	0.6426828503608704
concepts[0].wikidata	https://www.wikidata.org/wiki/Q1304193
concepts[0].display_name	Vertex (graph theory)
concepts[1].id	https://openalex.org/C73555534
concepts[1].level	2
concepts[1].score	0.642094612121582
concepts[1].wikidata	https://www.wikidata.org/wiki/Q622825
concepts[1].display_name	Cluster analysis
concepts[2].id	https://openalex.org/C117220453
concepts[2].level	2
concepts[2].score	0.5972386002540588
concepts[2].wikidata	https://www.wikidata.org/wiki/Q5172842
concepts[2].display_name	Correlation
concepts[3].id	https://openalex.org/C114614502
concepts[3].level	1
concepts[3].score	0.4146224558353424
concepts[3].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[3].display_name	Combinatorics
concepts[4].id	https://openalex.org/C33923547
concepts[4].level	0
concepts[4].score	0.3766694664955139
concepts[4].wikidata	https://www.wikidata.org/wiki/Q395
concepts[4].display_name	Mathematics
concepts[5].id	https://openalex.org/C105795698
concepts[5].level	1
concepts[5].score	0.2565317749977112
concepts[5].wikidata	https://www.wikidata.org/wiki/Q12483
concepts[5].display_name	Statistics
concepts[6].id	https://openalex.org/C132525143
concepts[6].level	2
concepts[6].score	0.18592065572738647
concepts[6].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[6].display_name	Graph
concepts[7].id	https://openalex.org/C2524010
concepts[7].level	1
concepts[7].score	0.11191782355308533
concepts[7].wikidata	https://www.wikidata.org/wiki/Q8087
concepts[7].display_name	Geometry
keywords[0].id	https://openalex.org/keywords/vertex
keywords[0].score	0.6426828503608704
keywords[0].display_name	Vertex (graph theory)
keywords[1].id	https://openalex.org/keywords/cluster-analysis
keywords[1].score	0.642094612121582
keywords[1].display_name	Cluster analysis
keywords[2].id	https://openalex.org/keywords/correlation
keywords[2].score	0.5972386002540588
keywords[2].display_name	Correlation
keywords[3].id	https://openalex.org/keywords/combinatorics
keywords[3].score	0.4146224558353424
keywords[3].display_name	Combinatorics
keywords[4].id	https://openalex.org/keywords/mathematics
keywords[4].score	0.3766694664955139
keywords[4].display_name	Mathematics
keywords[5].id	https://openalex.org/keywords/statistics
keywords[5].score	0.2565317749977112
keywords[5].display_name	Statistics
keywords[6].id	https://openalex.org/keywords/graph
keywords[6].score	0.18592065572738647
keywords[6].display_name	Graph
keywords[7].id	https://openalex.org/keywords/geometry
keywords[7].score	0.11191782355308533
keywords[7].display_name	Geometry
language	en
locations[0].id	pmh:oai:drops-oai.dagstuhl.de:20048
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306402524
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	False
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	Leibniz-Zentrum für Informatik (Schloss Dagstuhl)
locations[0].source.host_organization	https://openalex.org/I2799853480
locations[0].source.host_organization_name	Schloss Dagstuhl – Leibniz Center for Informatics
locations[0].source.host_organization_lineage	https://openalex.org/I2799853480
locations[0].license	cc-by
locations[0].pdf_url
locations[0].version	publishedVersion
locations[0].raw_type	InProceedings
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name
locations[0].landing_page_url	https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.8
locations[1].id	pmh:oai:arXiv.org:2402.10335
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license	cc-by
locations[1].pdf_url	https://arxiv.org/pdf/2402.10335
locations[1].version	submittedVersion
locations[1].raw_type	text
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published	False
locations[1].raw_source_name
locations[1].landing_page_url	http://arxiv.org/abs/2402.10335
locations[2].id	doi:10.48550/arxiv.2402.10335
locations[2].is_oa	True
locations[2].source.id	https://openalex.org/S4306400194
locations[2].source.issn
locations[2].source.type	repository
locations[2].source.is_oa	True
locations[2].source.issn_l
locations[2].source.is_core	False
locations[2].source.is_in_doaj	False
locations[2].source.display_name	arXiv (Cornell University)
locations[2].source.host_organization	https://openalex.org/I205783295
locations[2].source.host_organization_name	Cornell University
locations[2].source.host_organization_lineage	https://openalex.org/I205783295
locations[2].license	cc-by
locations[2].pdf_url
locations[2].version
locations[2].raw_type	article
locations[2].license_id	https://openalex.org/licenses/cc-by
locations[2].is_accepted	False
locations[2].is_published
locations[2].raw_source_name
locations[2].landing_page_url	https://doi.org/10.48550/arxiv.2402.10335
locations[3].id	doi:10.4230/lipics.swat.2024.8
locations[3].is_oa	True
locations[3].source.id	https://openalex.org/S7407052059
locations[3].source.type	repository
locations[3].source.is_oa	False
locations[3].source.issn_l
locations[3].source.is_core	False
locations[3].source.is_in_doaj	False
locations[3].source.display_name	Dagstuhl Research Online Publication Server
locations[3].source.host_organization
locations[3].source.host_organization_name
locations[3].license	cc-by
locations[3].pdf_url
locations[3].version
locations[3].raw_type
locations[3].license_id	https://openalex.org/licenses/cc-by
locations[3].is_accepted	False
locations[3].is_published
locations[3].raw_source_name
locations[3].landing_page_url	https://doi.org/10.4230/lipics.swat.2024.8
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5086072107
authorships[0].author.orcid
authorships[0].author.display_name	Matthias Bentert
authorships[0].author_position	first
authorships[0].raw_author_name	Bentert, Matthias
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5092050139
authorships[1].author.orcid	https://orcid.org/0009-0004-5466-3181
authorships[1].author.display_name	Alex Crane
authorships[1].author_position	middle
authorships[1].raw_author_name	Crane, Alex
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5064442594
authorships[2].author.orcid	https://orcid.org/0000-0001-7228-6640
authorships[2].author.display_name	Pål Grønås Drange
authorships[2].author_position	middle
authorships[2].raw_author_name	Drange, Pål Grønås
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5049595624
authorships[3].author.orcid	https://orcid.org/0000-0002-2354-3003
authorships[3].author.display_name	Felix Reidl
authorships[3].author_position	middle
authorships[3].raw_author_name	Reidl, Felix
authorships[3].is_corresponding	False
authorships[4].author.id	https://openalex.org/A5089650657
authorships[4].author.orcid	https://orcid.org/0000-0001-7720-6208
authorships[4].author.display_name	Blair D. Sullivan
authorships[4].author_position	last
authorships[4].raw_author_name	Sullivan, Blair D.
authorships[4].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.8
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2024-02-20T00:00:00
display_name	Correlation Clustering with Vertex Splitting
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10637
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9240000247955322
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1702
primary_topic.subfield.display_name	Artificial Intelligence
primary_topic.display_name	Advanced Clustering Algorithms Research
related_works	https://openalex.org/W1979597421, https://openalex.org/W2007980826, https://openalex.org/W4245490552, https://openalex.org/W2061531152, https://openalex.org/W3002753104, https://openalex.org/W2077600819, https://openalex.org/W1587224694, https://openalex.org/W2042127053, https://openalex.org/W2142036596, https://openalex.org/W3111310291
cited_by_count	0
locations_count	4
best_oa_location.id	pmh:oai:drops-oai.dagstuhl.de:20048
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306402524
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	False
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	Leibniz-Zentrum für Informatik (Schloss Dagstuhl)
best_oa_location.source.host_organization	https://openalex.org/I2799853480
best_oa_location.source.host_organization_name	Schloss Dagstuhl – Leibniz Center for Informatics
best_oa_location.source.host_organization_lineage	https://openalex.org/I2799853480
best_oa_location.license	cc-by
best_oa_location.pdf_url
best_oa_location.version	publishedVersion
best_oa_location.raw_type	InProceedings
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name
best_oa_location.landing_page_url	https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.8
primary_location.id	pmh:oai:drops-oai.dagstuhl.de:20048
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306402524
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	False
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	Leibniz-Zentrum für Informatik (Schloss Dagstuhl)
primary_location.source.host_organization	https://openalex.org/I2799853480
primary_location.source.host_organization_name	Schloss Dagstuhl – Leibniz Center for Informatics
primary_location.source.host_organization_lineage	https://openalex.org/I2799853480
primary_location.license	cc-by
primary_location.pdf_url
primary_location.version	publishedVersion
primary_location.raw_type	InProceedings
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name
primary_location.landing_page_url	https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.8
publication_date	2024-02-15
publication_year	2024
referenced_works_count	0
abstract_inverted_index.a	10, 54, 65
abstract_inverted_index.7.	71
abstract_inverted_index.In	72
abstract_inverted_index.We	0, 28
abstract_inverted_index.an	90
abstract_inverted_index.by	59, 83
abstract_inverted_index.in	22, 40
abstract_inverted_index.is	92
abstract_inverted_index.of	25, 75
abstract_inverted_index.to	110
abstract_inverted_index.we	52, 78, 100
abstract_inverted_index.0$.	98
abstract_inverted_index.For	45
abstract_inverted_index.and	4, 43, 63, 86, 108
abstract_inverted_index.any	95
abstract_inverted_index.are	33
abstract_inverted_index.for	94
abstract_inverted_index.its	5
abstract_inverted_index.new	11
abstract_inverted_index.the	23, 60, 73, 102, 111
abstract_inverted_index.yet	35
abstract_inverted_index.both	31
abstract_inverted_index.case	74
abstract_inverted_index.face	24
abstract_inverted_index.link	104
abstract_inverted_index.show	53
abstract_inverted_index.size	62, 85
abstract_inverted_index.that	30, 88
abstract_inverted_index.they	36
abstract_inverted_index.when	57, 81
abstract_inverted_index.with	9, 48, 68, 113
abstract_inverted_index.which	17
abstract_inverted_index.Vertex	50
abstract_inverted_index.called	13
abstract_inverted_index.extend	101
abstract_inverted_index.factor	70
abstract_inverted_index.kernel	56
abstract_inverted_index.vertex	15, 115
abstract_inverted_index.$ε>	97
abstract_inverted_index.Cluster	2, 46
abstract_inverted_index.Editing	3, 47
abstract_inverted_index.NP-hard	93
abstract_inverted_index.between	105
abstract_inverted_index.develop	64
abstract_inverted_index.exhibit	37
abstract_inverted_index.explore	1
abstract_inverted_index.finding	19
abstract_inverted_index.setting	112
abstract_inverted_index.Multicut	109
abstract_inverted_index.NP-hard,	34
abstract_inverted_index.clusters	21
abstract_inverted_index.constant	96
abstract_inverted_index.problems	32
abstract_inverted_index.solution	61, 84
abstract_inverted_index.addresses	18
abstract_inverted_index.algorithm	67
abstract_inverted_index.computing	89
abstract_inverted_index.determine	29
abstract_inverted_index.establish	79
abstract_inverted_index.operation	12
abstract_inverted_index.splitting	16
abstract_inverted_index.uncertain	26
abstract_inverted_index.Clustering	8, 107
abstract_inverted_index.Permissive	49
abstract_inverted_index.Splitting,	51
abstract_inverted_index.complexity	42
abstract_inverted_index.permissive	14, 114
abstract_inverted_index.polynomial	55
abstract_inverted_index.splitting.	116
abstract_inverted_index.Clustering,	77
abstract_inverted_index.Correlation	7, 76, 106
abstract_inverted_index.demonstrate	87
abstract_inverted_index.differences	39
abstract_inverted_index.established	103
abstract_inverted_index.overlapping	20
abstract_inverted_index.significant	38
abstract_inverted_index.information.	27
abstract_inverted_index.Additionally,	99
abstract_inverted_index.approximation	69
abstract_inverted_index.parameterized	41, 58, 82
abstract_inverted_index.generalization	6
abstract_inverted_index.polynomial-time	66
abstract_inverted_index.approximability.	44
abstract_inverted_index.para-NP-hardness	80
abstract_inverted_index.$n^{1-ε}$-approximation	91
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	5
citation_normalized_percentile