The Two Bicliques Problem is in NP intersection coNP
  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. 
M. A. Shalu and S. Vijayakumar
cs.CC cs.DS math.CO