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.
| Original language | English |
|---|
| Place of Publication | Tilburg |
|---|
| Publisher | Operations research |
|---|
| Number of pages | 5 |
|---|
| Volume | 789 |
|---|
| Publication status | Published - 2000 |
|---|
| Name | FEW Research Memorandum |
|---|
| Volume | 789 |
|---|