Dureté de CLIQUE paramétrée?

Soit $0\le p\le 1$ et considérons le problème de décision

CLIQUE p entrée: nombre entier s , graphe G avec t sommets et bords Question: ne contient une clique sur au moins les sommets?$_p$
$s$$G$$t$$\lceil p\binom{t}{2} \rceil$
$G$$s$

Une instance de CLIQUE contient une proportion sur toutes les arêtes possibles. Il est clair que CLIQUE est facile pour certaines valeurs de . CLIQUE contient uniquement des graphiques complètement déconnectés et CLIQUE contient des graphiques complets. Dans les deux cas, CLIQUE peut être décidé en temps linéaire. En revanche, pour des valeurs de proches de , CLIQUE est NP-difficile par une réduction de CLIQUE lui-même: il suffit essentiellement de prendre l'union disjointe avec le graphe de Turán T (t, s-1) . p p p 0 1 p$_p$$p$$_p$$p$$_0$$_1$$_p$$p$$1/2$$_p$ $T(t,s-1)$

Ma question:

CLIQUE $_p$ en PTIME ou NP-complet pour chaque valeur de $p$ ? Ou existe-t-il des valeurs de $p$ pour lesquelles CLIQUE $_p$ a une complexité intermédiaire (si P ≠ NP)?

Cette question est née d'une question connexe pour les hypergraphes, mais elle semble intéressante en soi.

Je suppose que le nombre dans la définition du problème CLIQUE _p est exactement égal au nombre d'arêtes dans le graphique, contrairement au commentaire de gphilip à la question.$\left\lceil p \binom{t}{2} \right\rceil$

Le problème CLIQUE _p est NP-complet pour toute constante rationnelle 0 < p <1 par une réduction du problème CLIQUE habituel. (L'hypothèse que p est rationnel n'est nécessaire que pour que puisse être calculé à partir de N dans le polynôme temporel dans N. )$\lceil pN \rceil$

Soit k ≥3 un entier satisfaisant à la fois k ² ≥1 / p et (1−1 / k ) (1−2 / k )> p . Étant donné un graphique G avec n sommets et m arêtes avec une valeur de seuil s , la réduction fonctionne comme suit.

1. Si s < k , nous résolvons le problème CLIQUE en temps O ( n ^s ) temps. S'il existe une clique de taille au moins s , nous produisons une instance de oui fixe. Sinon, nous produisons une no-instance fixe.
2. Si n < s , nous produisons une non-instance fixe.
3. Si n ≥ s ≥ k , on ajoute à G un graphe ( k −1) -partite où chaque ensemble se compose de n sommets qui ont exactement bords et produire ce graphique.$\left\lceil p \binom{nk}{2} \right\rceil - m$

Notons que le cas 1 prend O ( n ^{k −1} ) temps, qui est polynomial en n pour chaque p . Le cas 3 est possible car si n ≥ s ≥ k , alors est non négatif et tout au plus le nombre d'arêtes dans le complet ( k −1) graphique -partite K _{n , ..., n} comme le montrent les deux revendications qui suivent.$\left\lceil p \binom{nk}{2} \right\rceil - m$

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

Preuve . Puisque , il suffit de prouver , ou de manière équivalente pnk ( nk −1) ≥ n ( n -1). Puisque p ≥ 1 / k ² , on a 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}$

Réclamation 2 . . (Notez que le côté droit est le nombre d'arêtes dans le graphe complet K (1) -parti K _{n ,…, n} .)$\left\lceil p \binom{nk}{2} \right\rceil - m \lt n^2 \binom{k-1}{2}$

Preuve . Puisque et m ≥ 0, il suffit de prouver , ou de façon équivalente n ² ( k -1) ( k -2) - pnk ( nk -1) - 2 ≥ 0. Puisque p <(1−1 / k ) (1−2 / k ), nous avons QED .p ( n $\lceil x \rceil \lt x+1$ n2(k-1)(k-2)-pnk(nk-1)-2≥n2(k-1)(k-2)-n(n-$p \binom{nk}{2} + 1 \le n^2 \binom{k-1}{2}$

Edit : la réduction dans la révision 1 avait une erreur; il fallait parfois un graphe avec un nombre d'arêtes négatif (quand p était petit). Cette erreur est maintenant corrigée.

Si peut être fonction de t , alors le problème peut être intermédiaire. Configurez p de sorte que le nombre d'arêtes soit égal à log 4 t . Alors évidemment s peut être au plus log 2 t et donc il y a un algorithme t log 2 t pour ce problème, ce qui signifie que le problème (sous des hypothèses standard, disons que SAT n'a pas d'algorithmes sous-exponentiels) ne peut pas être NP dur.$p$$t$$p$$\log^4 t$$s$$\log^2 t$$t^{\log^2 t}$

$\log^2 t$

$p$