Improved Kernelization and Fixed-parameter Algorithms for Bicluster Editing

Abstract

Given a bipartite graph $G$, the \textsc{Bicluster Editing} problem asks for the minimum number of edges to insert or delete in $G$ so that every connected component is a bicluster, i.e. a complete bipartite graph. This has several applications, including in bioinformatics and social network analysis. In this work, we study the parameterized complexity under the natural parameter $k$, which is the number of allowed modified edges. We first show that one can obtain a kernel with $4.5k$ vertices, an improvement over the previously known quadratic kernel. We then propose an algorithm that runs in time $O^{\ast }(2.581^k)$. Our algorithm has the advantage of being conceptually simple and should be easy to implement.

The author acknowledges the contributions of Benoît Charbonneau and Pierre-Luc Parent for their help in finding the $4.5k$ lower bound on the kernel size