Fast biclustering by dual parameterization

DOI10.4230/LIPICS.IPEC.2015.402MaRDI QIDQ5363792zbMATH OpenOpenAlexFDO

Authors Pål Grønås Drange, Felix Reidl, Fernando Sánchez Villaamil, Somnath Sikdar

Publication date 29 September 2017

Full work available at URL https://arxiv.org/abs/1507.08158

zbMATH Keywords

graph editingparameterized complexitysubexponential algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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 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 $2^{5sqrtpk}+O(n+m)$ for p-Starforest Editing and $2^{O(psqrtklog(pk))}+O(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 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.

Recommendations

• Faster parameterized algorithm for Bicluster Editing
• Improved Algorithms for Bicluster Editing
• Applying Modular Decomposition to Parameterized Bicluster Editing
• Applying modular decomposition to parameterized cluster editing problems
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters

Cited in

(12)

• Even better fixed-parameter algorithms for bicluster editing
• A simple and improved parameterized algorithm for bicluster editing
• Subexponential algorithm for d-cluster edge deletion: exception or rule?
• Parameterized low-rank binary matrix approximation
• Complexity of modification problems for reciprocal best match graphs
• Faster parameterized algorithm for Bicluster Editing
• Bi-objective optimization of biclustering with binary data
• Faster parameterized algorithms for \textsc{Bicluster Editing} and \textsc{Flip Consensus Tree}
• A survey of parameterized algorithms and the complexity of edge modification
• Improved kernelization and fixed-parameter algorithms for bicluster editing
• Cluster editing with overlapping communities
• Cluster editing with vertex splitting

This page was built for publication: Fast biclustering by dual parameterization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363792)