Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

CRC 901 – On-The-Fly Computing (OTF Computing) Show image information

CRC 901 – On-The-Fly Computing (OTF Computing)

Monday, 03.04.2017 | 14.00 Uhr | Fürstenallee 11, room F1.110

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

Title of the talk: "A Multivariante Complexity Analysis of Cluster Editing"


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.

The University for the Information Society