[Back]

D. Binkele-Raible, H. Fernau, S. Gaspers, M. Liedloff:
"Exact exponential-time algorithms for finding bicliques";
Information Processing Letters, 111 (2010), 2; 64 - 67.

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 ⊆ V , X ∩ Y = ∅, is a non-induced biclique if {x,y} ∈ E for any x ∈ X and y ∈ Y . The NP-complete problem of finding a non-induced (k₁,k₂)-biclique asks to decide whether G contains a non-induced biclique (X,Y) such that |X|=k₁ and |Y|=k₂. In this paper, we design a polynomial-space O(1.6914ⁿ)-time algorithm for this problem. It is based on an algorithm for bipartite graphs that runs in time O(1.30052ⁿ). In deriving this algorithm, we also exhibit a relation to the spare allocation problem known from memory chip fabrication.

exact exponential-time algorithms, NP-hard problem, complete bipartite subgraphs

http://dx.doi.org/10.1016/j.ipl.2010.10.020