En una pregunta anterior Algoritmo parametrizado para encontrar bicliques , pregunté si había algoritmos parametrizados rápidos para encontrar un -biclique en un gráfico de n vértices y aprendí que estaba abierto si es FPT wrt k . ¿Es lo mismo para contar las k × k -bicliques, o se sabe que esto es # W \ [ 1 \] -hard wrt k (o alguna otra noción de dureza)?
Sé que contar las bicliques inducidas son # W \ [ 1 \] -duro, expandiendo una reducción simple para encontrar un biclique inducido en la sección 4.5 en la tesis de Serge Gaspers .
fuente