Clustering with Locally Bounded Ignorance
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910218177216512 |
|---|---|
| author | Garvardt, Jaroslav Komusiewicz, Christian |
| author_facet | Garvardt, Jaroslav Komusiewicz, Christian |
| contents | In Correlation Clustering, the input is a graph $G=(V,E)$ with weight function $ω: {V \choose 2}\to Z$
and the task is to partition the vertex set into clusters such that
the total weight of edges between clusters and missing edges
inside clusters is minimized. Due to close connections
between Correlation Clustering and Edge Multicut,
deciding whether there is a partition with total cost at most $k$ is
FPT with respect to $k$ but a polynomial kernel is presumably
impossible. We study the influence of the structure of the fuzzy
edge graph, that is, the graph induced by the weight-0 edges, on the
problem complexity. We show in particular that Correlation
Clustering admits a polynomial problem kernel when parameterized
by $k+d$, where $d$ is the degeneracy of the fuzzy edge graph, and when
parameterized by $k+c$, where $c$ is the closure of the fuzzy edge
graph. We complement these positive results by showing hardness for
several settings where the graph induced by the edges and nonedges has very restricted structure. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_13917 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Clustering with Locally Bounded Ignorance Garvardt, Jaroslav Komusiewicz, Christian Data Structures and Algorithms Computational Complexity In Correlation Clustering, the input is a graph $G=(V,E)$ with weight function $ω: {V \choose 2}\to Z$ and the task is to partition the vertex set into clusters such that the total weight of edges between clusters and missing edges inside clusters is minimized. Due to close connections between Correlation Clustering and Edge Multicut, deciding whether there is a partition with total cost at most $k$ is FPT with respect to $k$ but a polynomial kernel is presumably impossible. We study the influence of the structure of the fuzzy edge graph, that is, the graph induced by the weight-0 edges, on the problem complexity. We show in particular that Correlation Clustering admits a polynomial problem kernel when parameterized by $k+d$, where $d$ is the degeneracy of the fuzzy edge graph, and when parameterized by $k+c$, where $c$ is the closure of the fuzzy edge graph. We complement these positive results by showing hardness for several settings where the graph induced by the edges and nonedges has very restricted structure. |
| title | Clustering with Locally Bounded Ignorance |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2605.13917 |