Kompleksitas parameter dari nomor persimpangan grafik

Bagaimana jika ada yang diketahui tentang kompleksitas parameter dari penghitungan angka perpotongan grafik (jumlah klik terkecil yang diperlukan untuk menutupi semua tepinya)?

Sudah lama dikenal sebagai NP-complete, dan itu jelas FPT karena memiliki kernel: jika Anda dapat menutupi grafik dengan klik maka ada paling banyak 2 k lingkungan simpul tertutup yang berbeda (dua simpul memiliki lingkungan yang sama jika mereka termasuk kelompok klik yang sama), dan Anda mungkin juga hanya memiliki satu simpul per lingkungan. Apakah pengamatan ini dalam literatur di suatu tempat? Ketergantungan seperti apa pada k yang diketahui?$k$$2^k$$k$

Masalahnya telah dipelajari dengan nama Edge Clique Cover, dan pengamatan yang Anda lakukan mengenai reduksi data telah digunakan untuk mendapatkan kernel dengan simpul 2 ^ k. Ini adalah masalah terbuka yang sudah lama ada apakah kernel polinomial ada. Saya tidak tahu tentang batas yang baik pada waktu berjalan, lihat http://theinf1.informatik.uni-jena.de/publications/clique-cover-jea07.pdf

Menjawab pertanyaan saya sendiri, sekarang ada pracetak pada arXiv yang menunjukkan bahwa eksponensial ganda adalah ketergantungan yang benar, dengan asumsi hipotesis waktu eksponensial . Lihat " Algoritma yang dikenal untuk COVER CLIQUE EDGE mungkin optimal ", Marek Cygan, Marcin Pilipczuk, dan Michał Pilipczuk, arXiv: 1203.1754 dan SODA 2013