Editing to Cliques: A Survey of FPT Results and Recent Applications in Analyzing Large Datasets

The Cluster Editing problem aims to transform an undirected graph into a vertex-disjoint union of cliques by adding or deleting at most kedges. It has been proven NP-hard several times as it has been discovered and rediscovered in important application areas. Most biologists, social scientists and other practitioners have databases and networks that need clustering. This paper describes four approaches to more realistically model what is found in practice: 1) Parameterized Complexity, kernelization, and the Cluster Editing Crown Reduction Rule, 2) Bigger, more aggressive, aggregate parameterization, 3) Fuzzy Cluster Editing and moving approximation into the modeling, and 4) Working “bottom-up” uniting kernelization and heuristics. Some applications are discussed.