9
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.