The Two Bicliques Problem is in NP intersection coNP

M. A. Shalu, S. Vijayakumar

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 comp…