A Fixed-Parameter Tractable Algorithm for Correlation Clustering with l Clusters
LI Shu-guang, Zhu Daming, Xin Xiao · 2010
Given a graph G=(V,E) with real positive edge weights, where each edge (u, v) is labeled either + or - depending on whether u and v have been deemed to be similar or dissimilar, the problem of correlation clustering with l clusters is to partition the vertices of G into at most l clusters to minimize the total weight of + edges between clusters and - edges within clusters. This problem for general graphs is APX-complete. A fixed-parameter tractable (FPT) algorithm is presented, where the parameter k is defined as the maximum, over all blocks B of the graph, of the number of vertices that must be removed from B to obtain a forest.