¿Qué pasa si se sabe algo sobre la complejidad parametrizada de calcular el número de intersección de un gráfico (el número más pequeño de camarillas necesario para cubrir todos sus bordes)?
Desde hace tiempo se sabe que es NP-completo, y obviamente es FPT porque tiene un núcleo: si puede cubrir un gráfico con camarillas, entonces hay a lo sumo barrios cerrados diferentes de vértices (dos vértices tienen los mismos barrios si pertenecen al mismo conjunto de camarillas), y también podría mantener solo un vértice por vecindario. ¿Es esta observación en la literatura en alguna parte? ¿Qué tipo de dependencia de se conoce?
fuente
Respondiendo a mi propia pregunta, ahora hay una preimpresión en arXiv que muestra que la doble exponencial es la dependencia correcta, suponiendo la hipótesis del tiempo exponencial . Consulte " Los algoritmos conocidos para EDGE CLIQUE COVER son probablemente óptimos ", Marek Cygan, Marcin Pilipczuk y Michał Pilipczuk, arXiv: 1203.1754 y SODA 2013
fuente