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

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?$k$$2^k$$k$

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

Répondant à ma propre question, il y a maintenant une préimpression sur arXiv montrant que la double exponentielle est la dépendance correcte, en supposant l' hypothèse de temps exponentielle . Voir « Les algorithmes connus pour EDGE CLIQUE COVER sont probablement optimaux », Marek Cygan, Marcin Pilipczuk et Michał Pilipczuk, arXiv: 1203.1754 et SODA 2013