# News

## Talk given by Dr. Faisal Abu-Khzam (Lebanese American University, Beirut, Lebanon)

Begin: Mon, 03. of Apr 2017 ( 2:00 PM)Location: Fürstenallee 11, room F1.110

On April 3rd, 2017, Dr. Faisal Abu-Khzam (Lebanese American University, Beirut, Lebanon) will give a talk about "A Multivariate 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.