# Comparison between the maximum clique and maximum biclique problem

It seems to be commonly believed that the maximum biclique problem (on a bipartite graph) is more difficult than the original maximum clique problem. Is there a formal proof for this claim? (For example, a reduction of the maximum clique problem to the maximum biclique problem.)

• Did you see Lin's SODA paper showing fpt reduction from $k$-biclique to $k$-clique? – R B Feb 12 '15 at 7:58
• I think you mean from k-clique to k-biclique, R B. Thus establishing W[1]-hardness of k-biclique from the known result for k-clique. – Andy Drucker Feb 12 '15 at 18:11
• Thanks a lot R B and Andy! I will look into this SODA paper. Also Thanks Jan for editing the questions! – Minkov Feb 12 '15 at 22:13
• Do you mean that proving hardness for the biclique problem is more difficult that proving hardness of the clique problem? or do you refer to the algorithms for solving the problems? – Igor Shinkar Apr 18 '18 at 20:28
• @IgorShinkar I am referring to the problem itself. – Minkov Apr 19 '18 at 6:39