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) on n vertices, a pair (X. Y), with X, Y subset of V, X boolean AND Y = mt set, is a non-induced biclique if {x, y} is an element of E for any x is an element of X and y is an element of Y. The NP-complete problem of finding a non-induced (k(1), k(2))-biclique asks to decide whether G contains a non-induced biclique (X. Y) such that vertical bar X vertical bar = k(1) and vertical bar Y vertical bar = k(2). In this paper, we design a polynomial-space O(1.6914(n))-time algorithm for this problem. It is based on an algorithm for bipartite graphs that runs in time O(1.30052(n)). 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(1.30052(n)). (C) 2010 Elsevier B.V. All rights reserved.