Polynomial-time algorithm to solve the maximum vertex bipartite subgraph problem I'm trying to find an algorithm that solves the maximum vertex biclique problem. I know that that algorithm can be solved in polynomial time (in contrast with the maximum edge biclique problem, which is NP-hard), and it's related somehow to transform the problem to a network flow problem, but I'm having a hard time finding it because most of the results from google are about NP-hard problems with similar wordings like maximum edge biclique problem, maximum vertex coverage and such.
Could anyone provide a link, explanation or even a pseudocode algorithm about how to solve the maximum vertex biclique problem in polynomial time?
The problem is equivalent to the Maximum Independent Set problem on the &quot;bipartite complement graph&quot; (take the complement graph and delete edges with both endpoints on the same side of the bipartition). Such an MIS is the complement of a Minimum Vertex Cover, which can itself be deduced from a Maximum Matching.
You can probably take it from here (with maybe a bit of googling for how to find a Minimum Vertex Cover in a bipartite graph).