Parametrized Complexity of Counting Bicliques

Question

In a previous question 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.

Answer 1

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.