Härte der parametrierten CLIQUE?

Sei $0\le p\le 1$ und betrachte das Entscheidungsproblem

CLIQUE p Input: Ganzzahl s , Graph G mit t Eckpunkten und Kanten Frage: hat enthält eine Clique auf mindestens Vertices?$_p$
$s$$G$$t$G$\lceil p\binom{t}{2} \rceil$
$G$$s$

Eine Instanz von CLIQUE enthält einen Anteil aller möglichen Kanten. Es ist klar, dass CLIQUE für einige Werte von einfach ist . CLIQUE enthält nur vollständig getrennte Diagramme, und CLIQUE enthält vollständige Diagramme. In beiden Fällen kann CLIQUE in linearer Zeit entschieden werden. Auf der anderen Seite, für die Werte von nahe bei , CLIQUE ist NP-hard durch eine Reduktion von CLIQUE mich: Im Wesentlichen ist es ausreichend , die disjunkte Vereinigung mit dem nehmen Turán Graph . p p p 0 1 p p 1 / 2 p T ( T , s - 1 $_p$$p$$_p$$p$$_0$$_1$$_p$$p$$1/2$$_p$ $T(t,s-1)$

Meine Frage:

Ist CLIQUE $_p$ für jeden Wert von p entweder in PTIME oder in NP-complete $p$? Oder gibt es p- Werte, $p$für die CLIQUE $_p$ eine mittlere Komplexität hat (wenn P ≠ NP ist)?

Diese Frage ergab sich aus einer verwandten Frage für Hypergraphen, scheint aber für sich genommen interessant zu sein.

Ich davon aus, dass die Zahl in der Definition des Problems CLIQUE _p genau der Anzahl der Kanten in der Grafik entspricht, im Gegensatz zu gphilips Kommentar zur Frage.$\left\lceil p \binom{t}{2} \right\rceil$

Das Problem CLIQUE _p ist für jede rationale Konstante 0 < p <1 NP-vollständig durch eine Reduktion von dem üblichen CLIQUE-Problem. (Die Annahme, dass p rational ist, ist nur erforderlich, damit aus N im in N berechnet werden kann .)$\lceil pN \rceil$

Sei k ≥3 eine ganze Zahl, die sowohl k ² ≥1 / p als auch (1−1 / k ) (1−2 / k )> p erfüllt . Bei einem Graphen G mit n Ecken und m Kanten zusammen mit einem Schwellenwert s funktioniert die Reduktion wie folgt.

1. Wenn s < k , lösen wir das CLIQUE-Problem in der Zeit O ( n ^s ). Wenn es eine Clique mit einer Größe von mindestens s gibt , erzeugen wir eine feste Ja-Instanz. Ansonsten erzeugen wir eine feste No-Instanz.
2. Wenn n < s ist , erzeugen wir eine feste No-Instanz.
3. Wenn n ≥ s ≥ k ist , addieren wir zu G ein ( k −1) -teiliges Diagramm, in dem jede Menge aus n Eckpunkten besteht, die genau Kanten haben , und erstellen Sie dieses Diagramm.$\left\lceil p \binom{nk}{2} \right\rceil - m$

Es ist zu beachten, dass der Fall 1 die Zeit O ( n ^{k - 1} ) benötigt, die in n für jedes p polynomisch ist . Der Fall 3 ist möglich, weil, wenn n ≥ s ≥ k ist , nichtnegativ ist und höchstens die Anzahl der Kanten im ( k −1) -Partit-Graph K _{n ,…, n} wie in den folgenden zwei Ansprüchen gezeigt.$\left\lceil p \binom{nk}{2} \right\rceil - m$

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

Beweis . Da , reicht es aus, wenn wir oder äquivalent pnk ( nk −1) ≥ n ( n) nachweisen −1). Da p ≥ 1 / k ^{2 ist} , haben wir pnk ( nk −1) ≥ n ( n −1 / k ) ≥ n ( n −1). QED . p ( n$m \le \binom{n}{2}$$p \binom{nk}{2} \ge \binom{n}{2}$

Anspruch 2 . . (Beachten Sie, dass die rechte Seite die Anzahl der Kanten im vollständigen (k − 1) -Partit-Graphen K_{n,…,n ist}.)$\left\lceil p \binom{nk}{2} \right\rceil - m \lt n^2 \binom{k-1}{2}$

Beweis . Da und m ≥ 0 ist, genügt es, wenn wir p ( n k beweisen$\lceil x \rceil \lt x+1$$p \binom{nk}{2} + 1 \le n^2 \binom{k-1}{2}$

Bearbeiten : Die Reduzierung in Revision 1 hatte einen Fehler; Manchmal war ein Graph mit einer negativen Anzahl von Kanten erforderlich (wenn p klein war). Dieser Fehler ist jetzt behoben.

$p$$t$$p$$\log^4 t$$s$$\log^2 t$$t^{\log^2 t}$

$\log^2 t$

$p$