Это должно быть #W [1] -hard по стандартному аргументу интерполяции. Вот примерный набросок.
Сначала рассмотрим многоцветную версию задачи о биклике: для данного графа, набор вершин которого разбит на классы , найдите биклик, содержащий ровно одну вершину из каждого набора. В отличие от Biclique, чей статус FPT открыт, эта многоцветная версия известна как W [1] -hard: есть легкое сокращение от клика. Я считаю, что это также должно быть #W [1] -hard.Икс1, ... ,Икс2 к
Для данного графа и разбиения, как указано выше, давайте получим новый граф , заменив каждую вершину независимым набором размера (и заменив каждое ребро между и на biclique). Теперь число биклик в является функцией от переменных . На самом деле, можно видеть, что эта функция является полиномом степени не более а коэффициент члена точно равен количеству разноцветных биклик вгг'ИксяИксяИксяИксJИкся×ИксJк × кг'2 кИкс1, ... ,Икс2 к2 кИкс1⋅ ⋯ ⋅Икс2 кг . Таким образом, подставляя достаточно много комбинаций значений в переменные и подсчитывая количество биклик в , мы можем оценить этот многочлен в достаточном количестве мест, чтобы восстановить его коэффициенты путем интерполяции.Иксяг'