  We show that the problem of deciding whether the vertex set of a graph can be
covered with at most two bicliques is in NP$\cap$coNP. We thus almost determine
the computational complexity of a problem whose status has remained open for
quite some time. Our result implies that a polynomial time algorithm for the
problem is more likely than it being NP-complete unless P = NP.
