On the complexity of multi-parameterized 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 constraints that bound the amounts of both edge-addition...
Saved in:
| Main Author: | |
|---|---|
| Format: | article |
| Published: |
2017
|
| Online Access: | http://hdl.handle.net/10725/7486 https://doi.org/10.1016/j.jda.2017.07.003 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://www.sciencedirect.com/science/article/pii/S1570866717300473 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513482159816706 |
|---|---|
| author | Abu-Khzam, Faisal |
| author_facet | Abu-Khzam, Faisal |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal |
| dc.date.none.fl_str_mv | 2017 2018-04-23T12:02:51Z 2018-04-23T12:02:51Z 2018-04-23 |
| dc.identifier.none.fl_str_mv | 1570-8675 http://hdl.handle.net/10725/7486 https://doi.org/10.1016/j.jda.2017.07.003 Abu-Khzam, F. N. (2017). On the complexity of multi-parameterized cluster editing. Journal of Discrete Algorithms, 45, 26-34. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://www.sciencedirect.com/science/article/pii/S1570866717300473 |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | Journal of Discrete Algorithms |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | On the complexity of multi-parameterized cluster editing |
| dc.type.none.fl_str_mv | Article info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| 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. 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. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | LAURepo_5accca3a95d25df2b9ecdf7cbfb91fb7 |
| identifier_str_mv | 1570-8675 Abu-Khzam, F. N. (2017). On the complexity of multi-parameterized cluster editing. Journal of Discrete Algorithms, 45, 26-34. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/7486 |
| publishDate | 2017 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | On the complexity of multi-parameterized cluster editingAbu-Khzam, FaisalThe 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.PublishedN/A2018-04-23T12:02:51Z2018-04-23T12:02:51Z20172018-04-23Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/article1570-8675http://hdl.handle.net/10725/7486https://doi.org/10.1016/j.jda.2017.07.003Abu-Khzam, F. N. (2017). On the complexity of multi-parameterized cluster editing. Journal of Discrete Algorithms, 45, 26-34.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttps://www.sciencedirect.com/science/article/pii/S1570866717300473enJournal of Discrete Algorithmsinfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/74862021-03-19T10:43:20Z |
| spellingShingle | On the complexity of multi-parameterized cluster editing Abu-Khzam, Faisal |
| status_str | publishedVersion |
| title | On the complexity of multi-parameterized cluster editing |
| title_full | On the complexity of multi-parameterized cluster editing |
| title_fullStr | On the complexity of multi-parameterized cluster editing |
| title_full_unstemmed | On the complexity of multi-parameterized cluster editing |
| title_short | On the complexity of multi-parameterized cluster editing |
| title_sort | On the complexity of multi-parameterized cluster editing |
| url | http://hdl.handle.net/10725/7486 https://doi.org/10.1016/j.jda.2017.07.003 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://www.sciencedirect.com/science/article/pii/S1570866717300473 |