We prove that the maximum edge biclique problem in bipartite graphs is NP-complete.A biclique in a bipartite graph is a vertex induced subgraph which is complete.The problem of finding a biclique with a maximum number of vertices is known to be solvable in polynomial time but the complexity of finding a biclique with a maximum number of edges was still undecided.
|Place of Publication||Tilburg|
|Number of pages||5|
|Publication status||Published - 2000|
|Name||FEW Research Memorandum|