Sparametryzowana złożoność numeru przecięcia wykresu

Co jeśli wiadomo o sparametryzowanej złożoności obliczania numeru przecięcia wykresu (najmniejszej liczby klików potrzebnych do pokrycia wszystkich jego krawędzi)?

Od dawna wiadomo, że jest NP-kompletny, i oczywiście FPT, ponieważ ma jądro: jeśli możesz pokryć wykres klikami, to istnieje co najwyżej różnych zamkniętych sąsiedztw wierzchołków (dwa wierzchołki mają te same sąsiedztwa jeśli należą do tego samego zestawu klików) i równie dobrze możesz zachować tylko jeden wierzchołek na sąsiedztwo. Czy jest to gdzieś w literaturze? Jaka zależność od jest znana?$k$$2^k$$k$

Problem został zbadany pod nazwą Edge Clique Cover, a obserwacje dotyczące redukcji danych zostały wykorzystane do uzyskania jądra z 2 ^ k wierzchołkami. Od dawna istnieje otwarty problem, czy istnieje jądro wielomianowe. Nie wiem o dobrych granicach czasu działania, patrz http://theinf1.informatik.uni-jena.de/publications/clique-cover-jea07.pdf

Odpowiadając na moje pytanie, teraz jest preprint na arXiv pokazujący, że podwójna wykładnicza jest poprawną zależnością, zakładając hipotezę o wykładniczym czasie . Zobacz „ Znane algorytmy dla EDGE CLIQUE COVER są prawdopodobnie optymalne ”, Marek Cygan, Marcin Pilipczuk i Michał Pilipczuk, arXiv: 1203.1754 i SODA 2013