2026-07-22T12:14:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5600 2024-03-06T10:36:38Z ddc:004 open_access

Fast Biclustering by Dual Parameterization Drange, Pål Grønås Reidl, Felix Sánchez Villaamil, Fernando Sikdar, Somnath graph editing subexponential algorithms parameterized complexity 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 NP-hard, 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 (p-Cluster 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 p-Starforest Editing and O(2^{O(p * sqrt(k) * log(pk))} + n + m) for p-Bicluster Editing. We obtain a similar result for the more general case of t-Partite p-Cluster 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pål Grønås Drange and Felix Reidl and Fernando Sánchez Villaamil and Somnath Sikdar 2015 Is Part Of LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2015.402 urn:nbn:de:0030-drops-56004 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.402 eng https://creativecommons.org/licenses/by/3.0/legalcode