Dureté de CLIQUE paramétrée?

17

Soit 0p1 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
sgtp(t2)
gs

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 ppppp01pp1/2p 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.

András Salamon
la source
1
question interessante !
Suresh Venkat
Pa est-il un nombre réel compris entre 0 et 1, ou p peut-il être fonction de t?
Robin Kothari
@Robin: Je n'ai pas précisé, les deux seraient intéressants.
András Salamon,
3
Si la proportion d'arêtes est une limite supérieure (et non une exigence de comptage exacte ou une limite inférieure), alors pour toute constante 0<p<1 ce problème est NP-difficile par réduction à partir de CLIQUE: Ajoutez un ensemble suffisamment grand de sommets isolés . La condition est-elle que les bords du nombre soient égaux à l'expression donnée? Ou quelle chose évidente me manque-t-il? :-)
gphilip
1
@gphilip: Comme vous le signalez, la réduction est immédiate si la proportion n'est qu'une limite supérieure; c'est pourquoi la question est formulée en termes de proportion exacte.
András Salamon

Réponses:

14

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.p(t2)

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. )pN

Soit k ≥3 un entier satisfaisant à la fois k 2 ≥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 nsk , on ajoute à G un graphe ( k −1) -partite où chaque ensemble se compose de n sommets qui ont exactement bords et produire ce graphique.p(nk2)-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 nsk , 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.p(nk2)-m

Revendication 1 . .p(nk2)-m0

Preuve . Puisque , il suffit de prouver , ou de manière équivalente pnk ( nk −1) ≥ n ( n -1). Puisque p ≥ 1 / k 2 , on a pnk ( nk −1) ≥ n ( n −1 / k ) ≥ n ( n −1). QED . p ( nkm(n2)p(nk2)(n2)

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 .)p(nk2)-m<n2(k-12)

Preuve . Puisque et m ≥ 0, il suffit de prouver , ou de façon équivalente n 2 ( k -1) ( k -2) - pnk ( nk -1) - 2 ≥ 0. Puisque p <(1−1 / k ) (1−2 / k ), nous avons QED .p ( n kX<X+1 n2(k-1)(k-2)-pnk(nk-1)-2n2(k-1)(k-2)-n(n-1p(nk2)+1n2(k-12)

n2(k-1)(k-2)-pnk(nk-1)-2
n2(k-1)(k-2)-n(n-1k)(k-1)(k-2)-2
=nk(k-1)(k-2)-2(k-1)(k-2)-20.

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.

Tsuyoshi Ito
la source
c'est le plus proche du phrasé spécifique, donc merci de l'avoir abordé. Le cas 3 est le plus proche de ce que j'avais en tête. Cependant, je ne suis pas le calcul - pourriez-vous développer un peu?
András Salamon
@ András Salamon: Terminé.
Tsuyoshi Ito
15

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.ptpJournal4tsJournal2ttJournal2t

Journal2t

p

Boaz Barak
la source