Universität Paderborn » SFB 901 » 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.

Dr. Faisal Abu-Khzam (Lebanese American University, Beirut, Lebanon)


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.