<p>Besides the recent W(1)-hardness result for the parametrized complexity of the biclique problem (pointed out by R B), <a href="http://www.sciencedirect.com/science/article/pii/S0166218X03003330" rel="nofollow">here</a> is a paper whose abstract gives some detailed information about the polynomial-time solvability of variants of biclique detection.</p>

CC BY-SA 3.0
2015-02-12T18:17:48.793Z
2015-02-12T18:17:48.793Z
Andy Drucker
<p>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.)</p>

CC BY-SA 3.0
2015-02-12T07:58:55.937Z
Did you see [Lin's](http://www-imai.is.s.u-tokyo.ac.jp/~lin/files/biclique.pdf) SODA paper showing fpt reduction from $k$-biclique to $k$-clique?
R B
CC BY-SA 3.0
2015-02-12T18:11:26.617Z
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
CC BY-SA 3.0
2015-02-12T22:13:51.753Z
Thanks a lot R B and Andy! I will look into this SODA paper. Also Thanks Jan for editing the questions!
Minkov
CC BY-SA 3.0
2018-04-18T20:28:01.983Z
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
CC BY-SA 3.0
2018-04-19T06:39:36.213Z
@IgorShinkar I am referring to the problem itself.
Minkov
<cc.complexity-theory><graph-theory><clique>
Comparison between the maximum clique and maximum biclique problem
Minkov
# Comparison between the maximum clique and maximum biclique problem

(Asked by: username_0 on 2015-02-12)

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

**Tags:** cc.complexity-theory, graph-theory, clique

> **Comments:**
> **username_1**: Did you see [Lin's](http://www-imai.is.s.u-tokyo.ac.jp/~lin/files/biclique.pdf) SODA paper showing fpt reduction from $k$-biclique to $k$-clique?  
> **username_2**: I think you mean from k-clique to k-biclique, username_1.  Thus establishing W[1]-hardness of k-biclique from the known result for k-clique.  
> **username_0**: Thanks a lot username_1 and Andy! I will look into this SODA paper. Also Thanks Jan for editing the questions!  
> **username_3**: 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?  
> **username_0**: @IgorShinkar I am referring to the problem itself.  

---

## 1 answers

### Answer by username_2 on 2015-02-12. Score: 2 | Accepted answer

Besides the recent W(1)-hardness result for the parametrized complexity of the biclique problem (pointed out by username_1), [here](http://www.sciencedirect.com/science/article/pii/S0166218X03003330) is a paper whose abstract gives some detailed information about the polynomial-time solvability of variants of biclique detection.


---

