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.)

  • 5
    $\begingroup$ Did you see Lin's SODA paper showing fpt reduction from $k$-biclique to $k$-clique? $\endgroup$ – R B Feb 12 '15 at 7:58
  • 2
    $\begingroup$ 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. $\endgroup$ – Andy Drucker Feb 12 '15 at 18:11
  • 1
    $\begingroup$ Thanks a lot R B and Andy! I will look into this SODA paper. Also Thanks Jan for editing the questions! $\endgroup$ – Minkov Feb 12 '15 at 22:13
  • $\begingroup$ 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? $\endgroup$ – Igor Shinkar Apr 18 '18 at 20:28
  • $\begingroup$ @IgorShinkar I am referring to the problem itself. $\endgroup$ – Minkov Apr 19 '18 at 6:39

Besides the recent W(1)-hardness result for the parametrized complexity of the biclique problem (pointed out by R B), here is a paper whose abstract gives some detailed information about the polynomial-time solvability of variants of biclique detection.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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