Параметризованная сложность числа пересечений графа

Что если что-либо известно о параметризованной сложности вычисления числа пересечений графа (наименьшее число кликов, необходимых для охвата всех его ребер)?

Давно известно, что он является NP-полным, и это, очевидно, FPT, потому что у него есть ядро: если вы можете покрыть граф кликами, то существует не более 2 k различных замкнутых окрестностей вершин (две вершины имеют одинаковые окрестности, если они принадлежат к одному и тому же набору кликов), и вы могли бы также сохранить только одну вершину на окрестность. Это наблюдение в литературе где-то? Какая зависимость от k известна?$k$$2^k$$k$

Эта проблема была изучена под названием Edge Clique Cover, и ваши наблюдения относительно сокращения данных были использованы для получения ядра с 2 ^ k вершинами. Это давняя открытая проблема, существует ли ядро ​​полинома. Я не знаю о хороших оценках времени выполнения, см. Http://theinf1.informatik.uni-jena.de/publications/clique-cover-jea07.pdf

Отвечая на мой собственный вопрос, теперь на arXiv есть препринт, показывающий, что двойная экспонента является правильной зависимостью, если принять гипотезу экспоненциального времени . См. « Известные алгоритмы для EDGE CLIQUE COVER, вероятно, оптимальны », Марек Сиган, Марцин Пилипчук и Михал Пилипчук, arXiv: 1203.1754 и SODA 2013