Complejidad parametrizada del número de intersección del gráfico

17

¿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?k2kk

David Eppstein
fuente

Respuestas:

17

El problema se ha estudiado con el nombre de Edge Clique Cover, y las observaciones que hace con respecto a la reducción de datos se han utilizado para obtener un núcleo con 2 ^ k vértices. Es un problema abierto de larga data si existe un núcleo polinomial. No sé acerca de los buenos límites en el tiempo de ejecución, consulte http://theinf1.informatik.uni-jena.de/publications/clique-cover-jea07.pdf

Bart Jansen
fuente
44
Evidentemente, un núcleo polinomial es inviable, de acuerdo con algunos desarrollos bastante recientes: arxiv.org/abs/1111.0570
Neeldhara