Complejidad Parametrizada del Conteo de Bicliques

9

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)?k×knkk×kW\[1\]k

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 .k×kW\[1\]

Andreas Björklund
fuente

Respuestas:

9

Esto debería ser #W [1] -duro por un argumento de interpolación estándar. Aquí hay un bosquejo aproximado.

Primero, considere la versión multicolor del problema biclique: dado un gráfico cuyo conjunto de vértices se divide en clases , encuentre un biclique que contenga exactamente un vértice de cada conjunto. A diferencia de Biclique, cuyo estado de FPT está abierto, se sabe que esta versión multicolor es W [1] -dura: hay una reducción fácil de la camarilla. Creo que también debería ser #W [1] -duro.X1,,X2k

GGXixiXiXjxi×xjk×kG2kx1,,x2k2kx1x2kGxiG

Daniel Marx
fuente
Gracias Daniel, ¡esto tiene mucho sentido! También acabo de descubrir que Marc Thurley lo demuestra #A [1] -hard crm.cat/mthurley/theses/diploma.pdf
Andreas Björklund
kk×k