Multi-parameterized Cluster Editing


Project Description:
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. In this project, 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 study the effect of multi-parameterization on the problem complexity as well as some real applications. Parameters are chosen in an attempt to better-model problems arising from application domains, especially Biology and Clinical research.



PI: Faisal N. Abu-Khzam

Funding: This project has been partially supported by the Lebanese American University under grant SRDC-t2013-45.

Publications:

F. N. Abu-Khzam. The Multi-Parameterized Cluster Editing Problem, in Proceedings of the 7th International Conference on Combinatorial Optimization and Applications (COCOA 2013), Lecture Notes in Computer Science, volume 8287, Chengdu, China, December 2013, pages 284-294.

F. N. Abu-Khzam. On the Complexity of Multi-Parameterized Cluster Editing Journal of Discrete Algorithms, volume 45, pages 26-34, 2017.

F. N. Abu-Khzam, J. Egan, S. Gaspers, A. Shaw and P. Shaw. Cluster Editing with Vertex Splitting, in Proceedings of the 5th International Symposium on Combinatorial Optimization (ISCO), Lecture Notes in Computer Science, volume 10856, Marrakesh, Morroco, April 2018, pages 1-13.

J. R. Barr, P. Shaw, F. N. Abu-Khzam and J. Chen. Combinatorial Text Classification: the effect of multi-parameterized correlation clustering, in Proceedings of the 1st International Conference on Graph Computing (GC), IEEE, 2019: 29-36.