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
    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$ 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
    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$ Apr 18, 2018 at 20:28
  • $\begingroup$ @IgorShinkar I am referring to the problem itself. $\endgroup$
    – Minkov
    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$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .