Paper Info
Title
On the Complexity of Multi-Parameterized Cluster Editing.
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 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. 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.
Year
DOI
Venue
2017
10.1016/j.jda.2017.07.003
Journal of Discrete Algorithms
Keywords
DocType
Volume
Cluster editing,Fixed-parameter tractability,Multi-parameterization,Kernelization
Journal
45
ISSN
Citations 
PageRank 
1570-8667
0
0.34
References 
Authors
0
1
Name
Order
Citations
PageRank
Faisal N. Abu Khzam140436.25