Correlation clustering for general graphs
Correlation clustering is a framework for partitioning the vertices of a signed graph into an optimal number of clusters without requiring the number of clusters to be specified in advance.\N\NIn [Lect. Notes Comput. Sci. 12976, 499--515 (2021; \url{doi:10.1007/978-3-030-86520-7_31})], \textit{D. Mandaglio} et al. showed that for general graphs satisfying the Global Weight Bound (GWB) condition, correlation clustering admits a 5-approximation algorithm.\N\NGiven a signed graph $\Gamma$, the objective of correlation clustering is to partition the vertex set $V$ to either minimize the sum of negative edges within clusters together with the sum of positive edges between clusters (the min-disagreement formulation), or equivalently, to maximize the sum of positive edges within clusters plus the sum of negative edges between clusters (the max-agreement formulation). These two formulations are equivalent in terms of optimal solutions and computational complexity, and both are NP-hard.\N\NThe central goal of correlation clustering is therefore to minimize the number of disagreements, defined as negative edges inside clusters and positive edges across different clusters.\N\NIn the paper under discussion, the author presents an algorithm for correlation clustering in the general case. She also establishes a necessary and sufficient condition under which the lower bound -- given by the maximum number of edge-disjoint weakly negative cycles -- is equal to the minimum number of disagreements. Moreover, she shows that her proposed algorithm yields a 2-approximation for a specific subclass of signed graphs.\N\NThe author aims to improve approximation results for correlation clustering on general signed graphs. As a natural direction for future work, it would be worthwhile to extend these results to broader subclasses of signed graphs, such as signed chordal graphs without forbidden subgraphs.\N\NOverall, the paper presents strong theoretical results that are valuable for researchers working on correlation clustering and related interdisciplinary applications.
- A mathematical bibliography of signed and gain graphs and allied areas
- Correlation Clustering
- Correlation clustering
- Correlation clustering in general weighted graphs
- Excluded minors, network decomposition, and multicommodity flow
- Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
- Probabilistic graphical models.
This page was built for publication: Correlation clustering for general graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6884407)
