On the complexity of multi-parameterized cluster editing

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal
dc.date.accessioned 2018-04-23T12:02:51Z
dc.date.available 2018-04-23T12:02:51Z
dc.date.copyright 2017 en_US
dc.date.issued 2018-04-23
dc.identifier.issn 1570-8675 en_US
dc.identifier.uri http://hdl.handle.net/10725/7486
dc.description.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 constraints that bound the amounts of both edge-additions and deletions per single vertex, as well as the size of a clique-cluster. We show that the problem remains -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. In other words, Cluster Editing can be solved efficiently when the number of false positives/negatives per single data element is expected to be small compared to the minimum cluster size. As a byproduct, we obtain a kernelization algorithm that delivers linear-size kernels when the two edge-edit bounds are small constants. en_US
dc.language.iso en en_US
dc.title On the complexity of multi-parameterized cluster editing en_US
dc.type Article en_US
dc.description.version Published en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.relation.journal Journal of Discrete Algorithms en_US
dc.journal.volume 45 en_US
dc.article.pages 26-34 en_US
dc.keywords Cluster editing en_US
dc.keywords Fixed-parameter tractability en_US
dc.keywords Multi-parameterization en_US
dc.keywords Kernelization en_US
dc.identifier.doi https://doi.org/10.1016/j.jda.2017.07.003 en_US
dc.identifier.ctation Abu-Khzam, F. N. (2017). On the complexity of multi-parameterized cluster editing. Journal of Discrete Algorithms, 45, 26-34. en_US
dc.author.email faisal.abukhzam@lau.edu.lb en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php en_US
dc.identifier.url https://www.sciencedirect.com/science/article/pii/S1570866717300473 en_US
dc.orcid.id 0000-0001-5221-8421 en_US
dc.author.affiliation Lebanese American University en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account