Parametrisierte Komplexität der Grafikschnittstellennummer

Was ist, wenn irgendetwas über die parametrisierte Komplexität der Berechnung der Schnittmenge eines Graphen bekannt ist (die kleinste Anzahl von Cliquen, die erforderlich sind, um alle seine Kanten abzudecken)?

Es ist seit langem bekannt, dass es NP-vollständig ist, und es ist offensichtlich FPT, weil es einen Kern hat: Wenn Sie einen Graphen mit Cliquen abdecken können, dann gibt es höchstens 2 k verschiedene geschlossene Nachbarschaften von Eckpunkten (zwei Eckpunkte haben die gleichen Nachbarschaften, wenn Sie gehören derselben Gruppe von Cliquen an, und Sie können auch nur einen Scheitelpunkt pro Nachbarschaft behalten. Ist diese Beobachtung in der Literatur irgendwo? Welche Art von Abhängigkeit von k ist bekannt?$k$$2^k$$k$

Das Problem wurde unter dem Namen Edge Clique Cover untersucht, und Ihre Beobachtungen zur Datenreduktion wurden verwendet, um einen Kernel mit 2 ^ k Eckpunkten zu erhalten. Es ist ein seit langem offenes Problem, ob ein Polynomkern existiert. Ich kenne keine guten Grenzen für die Laufzeit, siehe http://theinf1.informatik.uni-jena.de/publications/clique-cover-jea07.pdf

Beantwortet man meine eigene Frage, so gibt es jetzt einen Preprint auf arXiv, der zeigt, dass die doppelte Exponentialabhängigkeit die richtige ist, wenn man die Exponentialzeithypothese annimmt . Siehe " Bekannte Algorithmen für EDGE CLIQUE COVER sind wahrscheinlich optimal ", Marek Cygan, Marcin Pilipczuk und Michał Pilipczuk, arXiv: 1203.1754 und SODA 2013