Complexité paramétrée du comptage des bicliques

Dans une question précédente, Algorithme paramétré pour trouver des bicliques , je me suis demandé s'il y avait des algorithmes paramétrés rapides pour trouver un -biclique dans un graphe de sommets n et j'ai appris qu'il était ouvert s'il était FPT par rapport à k . Est-ce la même chose pour le comptage des k × k -bicliques, ou sait-on qu'il s'agit de # W \ [ 1 \] -hard wrt k (ou d'une autre notion de dureté)?$k\times k$$n$$k$$k\times k$$W\[1\]$$k$

Je sais que le comptage des -bicliques induits est # W \ [ 1 \] -hard, élargissant une réduction simple pour trouver un biclique induit dans la section 4.5 de la thèse de Serge Gaspers .$k\times k$$W\[1\]$

Cela devrait être #W [1] -hard par un argument d'interpolation standard. Voici un croquis approximatif.

Considérons d'abord la version multicolore du problème biclique: étant donné un graphe dont l'ensemble des sommets est partitionné en classes , trouvez un biclique contenant exactement un sommet de chaque ensemble. Contrairement à Biclique, dont le statut FPT est ouvert, cette version multicolore est connue pour être W [1] -hard: il y a une réduction facile de la clique. Je pense qu'il devrait également être #W [1] -hard.$X_1,\dots, X_{2k}$

$G$$G'$$X_i$$x_i$$X_i$$X_j$$x_i\times x_j$$k\times k$$G'$$2k$$x_1,\dots,x_{2k}$$2k$$x_1\cdot\dots\cdot x_{2k}$$G$$x_i$$G'$