The biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most "k" bicliques (complete bipartite subgraphs).
It has been shown that "Biclique Vertex-Cover" is not fixed-parameter tractable unless P = NP in Covering Graphs with Few Complete Bipartite Subgraphs.
Most of the work in the literature proved the hardness of the problem in general/special cases. However, I need an exact algorithm for solving this problem on bipartite graphs. An approximate algorithm with a guarantee is also good (I'm aware of "Clustering and the Biclique Partition Problem", but it provided an approx solution for "Biclique Vertex Partition" not vertex-cover i.e. the provided solution is for disjoint bicliques not possibly overlapped ones).
Is anyone aware of an exact algorithm for "biclique vertex-cover" problem? Potentially, with time complexity analysis?
A naive algorithm, perhaps, would be starting from the whole bipartite graph to check for a biclique that covers all vertices (covering with one biclique). If not successful, we check subsets by removing one vertex and investigate if there exist two bicliques in this set that cover all vertices (trying to cover with two bicliques), and so on (trying to cover with more bicliques until reaching "k").