Sparametryzowana złożoność liczenia rowerów

W poprzednim pytaniu Sparametryzowany algorytm znajdowania biklików zapytałem, czy istnieją szybkie sparametryzowane algorytmy do znalezienia$k\times k$-biclique in an $n$ wykres wierzchołków i dowiedziałem się, że był otwarty, jeśli jest FPT wrt $k$. To samo odnosi się do liczenia$k\times k$-bikiety, czy wiadomo, że to #$W\[1\]$-hard wrt $k$ (lub jakieś inne pojęcie twardości)?

Wiem, że liczenie wywołanej $k\times k$-bikiety są #$W\[1\]$- twarda, poszerzając prostą redukcję do znalezienia indukowanej biclique w sekcji 4.5 w pracy Serge'a Gaspersa .

Powinno to być #W [1] - twarde według standardowego argumentu interpolacji. Oto przybliżony szkic.

Najpierw rozważmy wielokolorową wersję problemu podwójnego: biorąc pod uwagę wykres, którego zestaw wierzchołków jest podzielony na klasy $X_1,\dots, X_{2k}$, znajdź biclique zawierającą dokładnie jeden wierzchołek z każdego zestawu. W przeciwieństwie do Biclique, którego status FPT jest otwarty, ta wielobarwna wersja jest znana jako twarda W [1]: łatwo można ją zmniejszyć od kliki. Uważam, że powinien to być również #W [1] -hard.

Biorąc pod uwagę wykres $G$ i podział jak wyżej, uzyskajmy nowy wykres $G'$ zastępując każdy wierzchołek $X_i$ z niezależnym zestawem rozmiarów $x_i$ (i zamiana każdej krawędzi pomiędzy $X_i$ i $X_j$ przez $x_i\times x_j$biclique). Teraz liczba$k\times k$ bicliques in $G'$ jest funkcją $2k$ zmienne $x_1,\dots,x_{2k}$. W rzeczywistości widać, że ta funkcja jest co najwyżej wielomianem stopnia$2k$ i współczynnik tego terminu $x_1\cdot\dots\cdot x_{2k}$ jest dokładnie liczbą wielokolorowych bali $G$. Zatem przez podstawienie wystarczająco wielu kombinacji wartości w zmiennych$x_i$ i zliczanie liczby bicliques w $G'$, możemy ocenić ten wielomian w wystarczająco wielu miejscach, aby odzyskać jego współczynniki przez interpolację.