3
$\begingroup$

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

$\endgroup$
5
  • 5
    $\begingroup$ Did you see Lin's SODA paper showing fpt reduction from $k$-biclique to $k$-clique? $\endgroup$
    – R B
    Commented Feb 12, 2015 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$ Commented Feb 12, 2015 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
    Commented Feb 12, 2015 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$ Commented Apr 18, 2018 at 20:28
  • $\begingroup$ @IgorShinkar I am referring to the problem itself. $\endgroup$
    – Minkov
    Commented Apr 19, 2018 at 6:39

1 Answer 1

2
$\begingroup$

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.

$\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.