Exact exponential-time algorithms for finding bicliques

Due to a large number of applications, bicliques of graphs have been widely considered in the literature. This paper focuses on non-induced bicliques. Given a graph G=(V,E)G=(V,E) on n   vertices, a pair (X,Y)(X,Y), with X,Y⊆VX,Y⊆V, X∩Y=∅X∩Y=∅, is a non-induced biclique if {x,y}∈E{x,y}∈E for any x∈Xx∈X and y∈Yy∈Y. The NP-complete problem of finding a non-induced (k1,k2)(k1,k2)-biclique asks to decide whether G   contains a non-induced biclique (X,Y)(X,Y) such that |X|=k1|X|=k1 and |Y|=k2|Y|=k2. In this paper, we design a polynomial-space O(n1.6914)O(1.6914n)-time algorithm for this problem. It is based on an algorithm for bipartite graphs that runs in time O(n1.30052)O(1.30052n). In deriving this algorithm, we also exhibit a relation to the spare allocation problem known from memory chip fabrication. As a byproduct, we show that the constraint bipartite vertex cover problem can be solved in time O(n1.30052)O(1.30052n).

Research highlights► The problem of finding a non-induced (k1,k2)(k1,k2)-biclique is considered. ► An exact exponential-time algorithm for this problem is provided. ► A faster algorithm for the problem on bipartite graphs is given. ► The constraint bipartite vertex cover problem is also considered.