Twardość sparametryzowanego CLIQUE?

Niech $0\le p\le 1$ i rozważmy problem decyzyjny

Klika P Wejście: całkowita s , wykres G z T wierzchołki krawędzie Pytanie: sposób zawierać klika na co najmniej wierzchołki?$_p$
$s$$G$$t$G$\lceil p\binom{t}{2} \rceil$
$G$$s$

Instancja CLIQUE zawiera proporcję spośród wszystkich możliwych krawędzi. Wyraźnie CLIQUE jest łatwy dla niektórych wartości . CLIQUE zawiera tylko całkowicie odłączone wykresy, a CLIQUE zawiera pełne wykresy. W obu przypadkach CLIQUE można ustalić w czasie liniowym. Z drugiej strony, dla wartości zbliżonych do , CLIQUE jest NP-twardy przez redukcję z samego CLIQUE: zasadniczo wystarczy przyjąć rozłączny związek z wykresem Turána . P P P 0 1 P P 1 / 2 $_p$$p$$_p$$p$$_0$$_1$$_p$$p$$1/2$$_p$ $T(t,s-1)$

Moje pytanie:

Czy CLIQUE ma wartość PTIME lub NP-complete dla każdej wartości ? Czy są wartości dla których CLIQUE ma pośrednią złożoność (jeśli P ≠ NP)? p p $_p$$p$$p$$_p$

To pytanie powstało z pokrewnego pytania dotyczącego hipergraphów, ale samo w sobie wydaje się interesujące.

Zakładam, że liczba w definicji problemu CLIQUE_pjest dokładnie równa liczbie krawędzi na wykresie, w przeciwieństwie do komentarza gphilipa do pytania.$\left\lceil p \binom{t}{2} \right\rceil$

Problem CLIQUE _p jest NP-zupełny dla dowolnej racjonalnej stałej 0 < p <1 poprzez zmniejszenie od zwykłego problemu CLIQUE. (Założenie, że p jest racjonalne, jest wymagane tylko po to, aby można było obliczyć z N w funkcji wielomianu czasowego w N ).$\lceil pN \rceil$

Niech k ≥3 będzie liczbą całkowitą spełniającą zarówno k ² ≥1 / p, jak i (1−1 / k ) (1−2 / k )> p . Biorąc pod uwagę wykres G z n wierzchołkami i krawędziami m wraz z wartością progową s , redukcja działa w następujący sposób.

1. Jeśli s < k , rozwiązujemy problem CLIQUE w czasie O ( n ^s ). Jeśli istnieje klika wielkości co najmniej s , tworzymy stałą instancję typu tak. W przeciwnym razie produkujemy stały brak wystąpienia.
2. Jeśli n < s , tworzymy stały brak wystąpienia.
3. Jeśli n ≥ s ≥ k , dodajemy do G a ( k -1) wykres partycypacyjny, gdzie każdy zestaw składa się z n wierzchołków, które mają dokładnie krawędzi i wygeneruj ten wykres.$\left\lceil p \binom{nk}{2} \right\rceil - m$

Należy zauważyć, że w przypadku 1 odbywa O ( N ^{K -1} ) czas, który jest wielomian n dla każdego p . Przypadek 3 jest możliwy, ponieważ jeśli n ≥ s ≥ k , to jest nieujemne i co najwyżej liczba krawędzi na pełnym (k-1) wykresie stronniczym K_n,…,n,jak pokazano w dwóch poniższych zastrzeżeniach.$\left\lceil p \binom{nk}{2} \right\rceil - m$

Roszczenie 1 . .$\left\lceil p \binom{nk}{2} \right\rceil - m \ge 0$

$m \le \binom{n}{2}$$p \binom{nk}{2} \ge \binom{n}{2}$

$\left\lceil p \binom{nk}{2} \right\rceil - m \lt n^2 \binom{k-1}{2}$. (Note that the right-hand side is the number of edges in the complete (k−1)-partite graph K_n,…,n.)

Proof. Since $\lceil x \rceil \lt x+1$ and m ≥ 0, it suffices if we prove $p \binom{nk}{2} + 1 \le n^2 \binom{k-1}{2}$, or equivalently n²(k−1)(k−2) − pnk(nk−1) − 2 ≥ 0. Since p < (1−1/k)(1−2/k), we have

Edit: The reduction in Revision 1 had an error; it sometimes required a graph with negative number of edges (when p was small). This error is fixed now.

If $p$ can be a function of $t$, then the problem can be intermediate. Set up $p$ so that the number of edges will be say $\log^4 t$. Then obviously $s$ can be at most $\log^2 t$ and hence there is a $t^{\log^2 t}$ algorithm for this problem, meaning that the problem (under standard assumptions, say SAT doesn't have subexponential algorithms) cannot be NP hard.

On the other hand, this problem is harder than the standard clique problem on $\log^2 t$ vertices (you can always place all the edges on those vertices and ignore the rest). And so again, under the same assumption the problem doesn't have a polynomial time algorithm.

If $p$ is a constant then it's always NP hard as gphilip said.