An FPT Algorithm for the Correlation Clustering Problem
Given an undirected graph G=(V, E) with real nonnegative weights and + or – labels on its edges, the correlation clustering problem is to partition the vertices of G into clusters to minimize the total weight of cut + edges and uncut – edges. This problem is APX-hard and has been intensively studied mainly from the viewpoint of polynomial time approximation algorithms. By way of contrast, a fixed-parameter tractable algorithm is presented that takes treewidth as the parameter, with a running time that is linear in the number of vertices of G.
X. Xin "An FPT Algorithm for the Correlation Clustering Problem", Key Engineering Materials, Vols. 474-476, pp. 924-927, 2011