On April 3, 2017, Dr. Faisal Abu-Khzam (Lebanese American University, Beirut, Lebanon) will give a talk about "A Multivariante Complexity Analysis of Cluster Editing" in the context of the SFB 901.
Abstract:
The Cluster Editing problem seeks a transformation of a given undirected graph into a disjoint union of cliques via a (minimum) number of edge additions or deletions. A multi-parameterized version of the problem is studied, featuring a number of input parameters that bound the amount of both edge-additions and deletions per single vertex, as well as the size of a clique-cluster.
We briefly overview previous work on the problem and show that it remains NP-hard even when only one edge can be deleted and at most two edges can be added per vertex. However, the new formulation allows us to solve Cluster Editing (exactly) in polynomial time when the number of edge-edit operations per vertex is smaller than half the minimum cluster size. As a byproduct, we obtain a simple kernelization algorithm that delivers linear-size kernels when the two edge-edit bounds are fixed constants.
We further discuss some practical aspects of the multi-parameterized approach and the impact of adding more parameters, such as the number of outliers. Some open problems and new research directions are also discussed.