Abstract
We study two clustering problems, Starforest Editing, the problem of adding and deleting edges to obtain a disjoint union of stars, and the generalization Bicluster Editing. We show that, in addition to being NPhard, none of the problems can be solved in subexponential time unless the exponential time hypothesis fails.
Misra, Panolan, and Saurabh (MFCS 2013) argue that introducing a bound on the number of connected components in the solution should not make the problem easier: In particular, they argue that the subexponential time algorithm for editing to a fixed number of clusters (pCluster Editing) by Fomin et al. (J. Comput. Syst. Sci., 80(7) 2014) is an exception rather than the rule. Here, p is a secondary parameter, bounding the number of components in the solution.
However, upon bounding the number of stars or bicliques in the solution, we obtain algorithms which run in time O(2^{3*sqrt(pk)} + n + m) for pStarforest Editing and O(2^{O(p * sqrt(k) * log(pk))} + n + m) for pBicluster Editing. We obtain a similar result for the more general case of tPartite pCluster Editing. This is subexponential in k for a fixed number of clusters, since p is then considered a constant.
Our results even out the number of multivariate subexponential time algorithms and give reasons to believe that this area warrants further study.
BibTeX  Entry
@InProceedings{drange_et_al:LIPIcs:2015:5600,
author = {Pål Gr\onås Drange and Felix Reidl and Fernando S{\'a}nchez Villaamil and Somnath Sikdar},
title = {{Fast Biclustering by Dual Parameterization}},
booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
pages = {402413},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897927},
ISSN = {18688969},
year = {2015},
volume = {43},
editor = {Thore Husfeldt and Iyad Kanj},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5600},
URN = {urn:nbn:de:0030drops56004},
doi = {10.4230/LIPIcs.IPEC.2015.402},
annote = {Keywords: graph editing, subexponential algorithms, parameterized complexity}
}
Keywords: 

graph editing, subexponential algorithms, parameterized complexity 
Collection: 

10th International Symposium on Parameterized and Exact Computation (IPEC 2015) 
Issue Date: 

2015 
Date of publication: 

19.11.2015 