Параметризованный алгоритм поиска бикликов

Для заданного ненаправленного графа из вершин, какова наилучшая известная оценка времени выполнения для нахождения подграфа, который является k × k -бикликом? Существуют ли более быстрые параметризованные алгоритмы, чем алгоритм времени для "угадывания" одной стороны биклика и проверки, есть ли хотя бы других вершин, инцидентных всем им?$n$$k\times k$$\binom{n}{k}\mbox{poly}(n)$$k$

Параметризованный вырождением или краткостью, это FPT. Более конкретно, где d - вырождение (или a 3 2 2 a для краткости). Видеть:$O(d^3 2^d n)$$d$$a^3 2^{2a}$

• Алгоритмы составления списков двусмысленности и двудольного подграфа. Д. Эппштейн. Inf. Proc. Lett. 51: 207-211, 1994 .

Еще одна параметризованная статья была только что принята к SWAT 2012 , на этот раз параметризованная самой длинной индуцированной длиной пути:

• Aistis Atminas, Вадим Лозин и Игорь Разгон: Алгоритм линейного времени для вычисления небольшого biclique в графах без длинных индуцированных путей. SWAT 2012, чтобы появиться.

Но я понимаю, что независимо от того, является ли это FPT или нет с естественным параметром (размером biclique), это большая открытая проблема.

Следующие статьи предоставляют алгоритмы экспоненциального времени для неиндуцированной бикликовой задачи и могут быть вам интересны:

• Даниэль Бинкле-Рейбл, Хеннинг Фернэу, Серж Гасперс, Матье Лидлофф: Точные экспоненциально-временные алгоритмы поиска бикликов . Inf. Процесс. Lett. 111 (2): 64-67 (2010)

• Жан-Франсуа Кутюрье, Дитер Крач: Двухцветные независимые наборы
  и биклики . Inf. Процесс. Lett. 112 (8-9): 329-334 (2012)

В этом приближении Б. Эймса и С. Вавасиса «Минимизация ядерной нормы для посаженных задач клики и биклика» ( http://arxiv.org/pdf/0901.3348.pdf ) обнаруживается биклик для некоторого конкретного типа графов в поли- время, но не имеет общих гарантий приближения.

Авторы преобразовывают проблему biclique в минимизацию ранга с учетом аффинных ограничений. Затем они решают проблему релаксации, используя эвристику ядерной нормы, которую можно представить как SDP. Эта эвристика - довольно захватывающий гаджет из сжатой чувствительной атрибутики. Эта релаксация обычно допускает некоторые милые условия оптимальности, когда набор ограничений демонстрирует «соответствующий тип» случайности.

Стоит отметить, что найти ak по k biclique в графе n-вершин так же трудно, как найти клику размера k в (n / 2) -вершинном графе: просто возьмите (n / 2) вершинный граф, и преобразовать его в двудольный граф очевидным образом (каждая вершина v превращается в две вершины v1, v2, которые соединены ребром, а каждое ребро (u, v) превращается в два ребра: (u1, v2) и (u2 , v1)). Поскольку нахождение клики размера k является W [1] -твердым, то нахождение biclique также является W [1] -твердым, и поэтому предполагается, что алгоритм не имеет времени выполнения$n^{o(k)}$,