Sparametryzowany algorytm znajdowania biklików

Biorąc pod uwagę nieukierowany wykres $n$ wierzchołka, jaki jest najbardziej znany środowisko uruchomieniowe dla znalezienia podrozdziału, który jest dwukolorową $k\times k$ ? Czy istnieją szybsze algorytmy parametryzowane niż algorytm polegający na „zgadywaniu” jednej strony biclique i sprawdzanie, czy występuje co najmniej k innych wierzchołków przypadających na wszystkie z nich?$\binom{n}{k}\mbox{poly}(n)$$k$

Sparametryzowane przez degenerację lub arborność, to FPT. Mówiąc dokładniej, gdzie jest degeneracją (lub dla arboryczności). Widzieć:$O(d^3 2^d n)$$d$$a^3 2^{2a}$

• Algorytmy i dwuczęściowe algorytmy listowania podgraficznego. D. Eppstein. Inf. Proc. Łotysz. 51: 207–211, 1994 .

Kolejny sparametryzowany papier został właśnie zaakceptowany do SWAT 2012 , tym razem sparametryzowany przez najdłuższą indukowaną długość ścieżki:

• Aistis Atminas, Vadim Lozin i Igor Razgon: Algorytm czasu liniowego do obliczania małej biclique na wykresach bez długich ścieżek indukowanych. SWAT 2012, aby się pojawić.

Rozumiem jednak, że niezależnie od tego, czy jest to FPT, czy nie, z parametrem naturalnym (rozmiarem biclique), jest to duży otwarty problem.

Poniższe artykuły przedstawiają algorytmy czasu wykładniczego dla nieindukowanego problemu podwójnego i mogą Cię zainteresować:

• Daniel Binkele-Raible, Henning Fernau, Serge Gaspers, Mathieu Liedloff: Dokładne algorytmy czasu wykładniczego do znajdowania bicliques . Inf. Proces. Łotysz. 111 (2): 64–67 (2010 r.)

• Jean-François Couturier, Dieter Kratsch: Dwukolorowe niezależne zestawy
  i bicliques . Inf. Proces. Łotysz. 112 (8–9): 329–334 (2012)

To przybliżenie „Minimalizacja normy jądrowej dla problemów z sadzoną kliką i biclique”, autorstwa B. Amesa i S. Vavasis ( http://arxiv.org/pdf/0901.3348.pdf ), znajduje dwuwiersz dla niektórych określonych typów wykresów w poli- czas, ale nie ma ogólnych gwarancji zbliżenia.

Autorzy przekształcają problem biclique na minimalizację rangi, z zastrzeżeniem ograniczeń afinicznych. Następnie rozwiązują relaksację za pomocą heurystycznej normy jądrowej, którą można uznać za SDP. Ta heurystyka jest dość ekscytującym gadżetem związanym ze skompresowanymi akcesoriami wykrywającymi. Ten relaks zazwyczaj dopuszcza pewne słodkie warunki optymalizacyjne, gdy zbiór ograniczeń wykazuje „odpowiedni rodzaj” losowości.

$n^{o(k)}$