Advertisement
Published in:
2011 | OriginalPaper | Chapter
On the Parameterized Complexity of Consensus Clustering
Authors : Martin Dörnfelder, Jiong Guo, Christian Komusiewicz, Mathias Weller
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given a collection
${\mathcal{C}}$
of partitions of a base set
S
, the NP-hard
Consensus Clustering
problem asks for a partition of
S
which has a total Mirkin distance of at most
t
to the partitions in
${\mathcal{C}}$
, where
t
is a nonnegative integer. We present a parameterized algorithm for
Consensus Clustering
with running time
$O(4.24^k\cdot k^3+|{\mathcal C}|\cdot |S|^2)$
, where
$k:=t/|{\mathcal{C}}|$
is the average Mirkin distance of the solution partition to the partitions of
${\mathcal{C}}$
. Furthermore, we strengthen previous hardness results for
Consensus Clustering
, showing that
Consensus Clustering
remains NP-hard even when all input partitions contain at most two subsets. Finally, we study a local search variant of
Consensus Clustering
, showing W[1]-hardness for the parameter “radius of the Mirkin-distance neighborhood”. In the process, we also consider a local search variant of the related
Cluster Editing
problem, showing W[1]-hardness for the parameter “radius of the edge modification neighborhood”.