<p>This should be #W[1]-hard by a standard interpolation argument. Here is a rough sketch.</p>

<p>First, consider the multicolored version of the biclique problem: given a graph whose set of vertices is partitioned into classes $X_1,\dots, X_{2k}$, find a biclique containing exactly one vertex from each set. Unlike Biclique, whose FPT status is open, this multicolored version is known to be W[1]-hard: there is an easy reduction from clique. I believe it should also be #W[1]-hard.</p>

<p>Given a graph $G$ and partition as above, let us obtain a new graph $G&#39;$ by replacing every vertex of $X_i$ with an independent set of size $x_i$ (and replacing each edge between $X_i$ and $X_j$ by an $x_i\times x_j$ biclique). Now the number of $k\times k$ bicliques in $G&#39;$ is a function of the $2k$ variables $x_1,\dots,x_{2k}$. In fact, one can see that this function is a polynomial of degree at most $2k$ and the coefficient of the term $x_1\cdot\dots\cdot x_{2k}$ is exactly the number of multicolored bicliques in $G$. Thus by substituting sufficiently many combination of values into the variables $x_i$ and counting the number of bicliques in $G&#39;$, we can evaluate this polynomial at sufficiently many places to recover its coefficients by interpolation.</p>

CC BY-SA 3.0
2012-04-10T11:15:20.957Z
Thank you Daniel, this makes perfect sense! I also just found that Marc Thurley proves it #A[1]-hard http://www.crm.cat/mthurley/theses/diploma.pdf
Andreas Björklund
CC BY-SA 3.0
2012-04-10T14:21:29.960Z
And the parsimonious reduction from $k$-clique to multicolored $k\times k$-biclique is in Appendix B in http://pages.cs.wisc.edu/~holger/papers/dm12soda.pdf
Andreas Björklund
CC BY-SA 3.0
2012-04-10T10:56:01.400Z
2012-04-10T10:56:01.400Z
Daniel Marx
<p>In a previous question <a href="https://cstheory.stackexchange.com/questions/10926/parametrized-algorithm-for-finding-bicliques">Parametrized Algorithm for Finding Bicliques</a>, I inquired if there were fast parametrized algorithms for finding a $k\times k$-biclique in an $n$ vertex graph and learnt that it was open if it is FPT w.r.t. $k$. Is the same true for <em>counting</em> the $k\times k$-bicliques, or is it known that this is #$W\[1\]$-hard w.r.t. $k$ (or some other notion of hardness)?</p>

<p>I know that counting <em>induced</em> $k\times k$-bicliques are #$W\[1\]$-hard, expanding a simple reduction for finding an induced biclique in section 4.5 in <a href="http://www.kr.tuwien.ac.at/drm/gaspers/SergeBookETA2010_screen.pdf" rel="nofollow noreferrer">Serge Gaspers' thesis</a>.</p>

<cc.complexity-theory><graph-theory><counting-complexity><parameterized-complexity>
Parametrized Complexity of Counting Bicliques
Andreas Björklund
# Parametrized Complexity of Counting Bicliques

(Asked by: username_0 on 2012-04-10)

In a previous question [Parametrized Algorithm for Finding Bicliques](https://cstheory.stackexchange.com/questions/10926/parametrized-algorithm-for-finding-bicliques), I inquired if there were fast parametrized algorithms for finding a $k\times k$-biclique in an $n$ vertex graph and learnt that it was open if it is FPT w.r.t. $k$. Is the same true for *counting* the $k\times k$-bicliques, or is it known that this is #$W\[1\]$-hard w.r.t. $k$ (or some other notion of hardness)?

I know that counting *induced* $k\times k$-bicliques are #$W\[1\]$-hard, expanding a simple reduction for finding an induced biclique in section 4.5 in [Serge Gaspers' thesis](http://www.kr.tuwien.ac.at/drm/gaspers/SergeBookETA2010_screen.pdf).

**Tags:** cc.complexity-theory, graph-theory, counting-complexity, parameterized-complexity

---

## 1 answers

### Answer by username_1 on 2012-04-10. Score: 9 | Accepted answer

This should be #W[1]-hard by a standard interpolation argument. Here is a rough sketch.

First, consider the multicolored version of the biclique problem: given a graph whose set of vertices is partitioned into classes $X\_1,\dots, X\_{2k}$, find a biclique containing exactly one vertex from each set. Unlike Biclique, whose FPT status is open, this multicolored version is known to be W[1]-hard: there is an easy reduction from clique. I believe it should also be #W[1]-hard.

Given a graph $G$ and partition as above, let us obtain a new graph $G'$ by replacing every vertex of $X\_i$ with an independent set of size $x\_i$ (and replacing each edge between $X\_i$ and $X\_j$ by an $x\_i\times x\_j$ biclique). Now the number of $k\times k$ bicliques in $G'$ is a function of the $2k$ variables $x\_1,\dots,x\_{2k}$. In fact, one can see that this function is a polynomial of degree at most $2k$ and the coefficient of the term $x\_1\cdot\dots\cdot x\_{2k}$ is exactly the number of multicolored bicliques in $G$. Thus by substituting sufficiently many combination of values into the variables $x\_i$ and counting the number of bicliques in $G'$, we can evaluate this polynomial at sufficiently many places to recover its coefficients by interpolation.

> **Comments:**
> **username_0**: Thank you Daniel, this makes perfect sense! I also just found that Marc Thurley proves it #A[1]-hard http://www.crm.cat/mthurley/theses/diploma.pdf  
> **username_0**: And the parsimonious reduction from $k$-clique to multicolored $k\times k$-biclique is in Appendix B in http://pages.cs.wisc.edu/~holger/papers/dm12soda.pdf  

---

