Show simple item record

dc.contributor.authorDrange, Pål Grønås
dc.contributor.authorReidl, Felix
dc.contributor.authorVillaamil, Fernando Sánchez
dc.contributor.authorSikdar, Somnath
dc.identifier.citationLeibniz International Proceedings in Informatics 2015, 43:402-413eng
dc.description.abstractWe 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.eng
dc.publisherDagstuhl Publishingeng
dc.rightsAttribution CC BY 3.0eng
dc.subjectgraph editingeng
dc.subjectsubexponential algorithmseng
dc.subjectparameterized complexityeng
dc.titleFast biclustering by dual parameterizationeng
dc.typeConference objecteng
dc.rights.holderCopyright Pål Grønås Drange, Felix Reidl, Fernando Sánchez Villaamil, and Somnath Sikdareng
bora.peerreviewedPeer reviewedeng
dc.type.documentJournal article
noa.nsiVDP::Matematikk og Naturvitenskap: 400eng

Files in this item


This item appears in the following Collection(s)

Show simple item record

Attribution CC BY 3.0
Except where otherwise noted, this item's license is described as Attribution CC BY 3.0