Complexité paramétrée du numéro d'intersection du graphe

17

Que faire si l'on sait quelque chose sur la complexité paramétrée du calcul du nombre d'intersection d'un graphe (le plus petit nombre de cliques nécessaires pour couvrir tous ses bords)?

Il est connu depuis longtemps pour être NP-complet, et c'est évidemment FPT car il a un noyau: si vous pouvez couvrir un graphique avec cliques, il y a au plus 2 k différents quartiers fermés de sommets (deux sommets ont les mêmes voisinages si ils appartiennent au même ensemble de cliques), et vous pourriez aussi bien ne garder qu'un seul sommet par quartier. Cette observation est-elle quelque part dans la littérature? Quel type de dépendance à k est connu?k2kk

David Eppstein
la source

Réponses:

17

Le problème a été étudié sous le nom de Edge Clique Cover, et les observations que vous faites concernant la réduction des données ont été utilisées pour obtenir un noyau avec 2 ^ k sommets. C'est un problème ouvert de longue date de savoir s'il existe un noyau polynomial. Je ne connais pas de bonnes limites sur le temps de fonctionnement, voir http://theinf1.informatik.uni-jena.de/publications/clique-cover-jea07.pdf

Bart Jansen
la source
4
De toute évidence, un noyau polynomial est irréalisable, selon certains développements assez récents: arxiv.org/abs/1111.0570
Neeldhara