1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

The problem is equivalent to the Maximum Independent Set problem on the "bipartite complement graph" (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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.