Härte der parametrierten CLIQUE?

17

Sei 0p1 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
sGtGsp(t2)
Gs

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 )pppp01pp1/2p T(t,s1)

Meine Frage:

Ist CLIQUE p für jeden Wert von p entweder in PTIME oder in NP-complete p? Oder gibt es p- Werte, pfü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.

András Salamon
quelle
1
interessante Frage !
Suresh Venkat
Ist pa eine reelle Zahl zwischen 0 und 1 oder kann p eine Funktion von t sein?
Robin Kothari
@Robin: Ich habe nicht angegeben, beide wären interessant.
András Salamon,
3
Wenn der Anteil der Kanten eine Obergrenze ist (und keine genaue Anzahl oder eine Untergrenze), dann ist dieses Problem für jede Konstante NP-schwer durch Reduktion von CLIQUE: Fügen Sie eine ausreichend große Menge isolierter Eckpunkte hinzu . Ist die Forderung , dass die Anzahl Kanten gleich den gegebenen Ausdruck? Oder was scheinbar Offensichtliche vermisse ich? :-)0<p<1
gphilip
1
@gphilip: Wie Sie bereits betont haben, erfolgt die Reduzierung sofort, wenn der Anteil nur eine Obergrenze ist. Aus diesem Grund wird die Frage in Bezug auf das genaue Verhältnis formuliert.
András Salamon,

Antworten:

14

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

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

Sei k ≥3 eine ganze Zahl, die sowohl k 2 ≥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 nsk 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.p(nk2)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 nsk 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.p(nk2)m

Anspruch 1 . .p(nk2)m0

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 ( nkm(n2)p(nk2)(n2)

Anspruch 2 . . (Beachten Sie, dass die rechte Seite die Anzahl der Kanten im vollständigen (k − 1) -Partit-Graphen Kn,…,n ist.)p(nk2)m<n2(k12)

Beweis . Da und m ≥ 0 ist, genügt es, wenn wir p ( n k beweisenx<x+1p(nk2)+1n2(k12)

n2(k1)(k2)pnk(nk1)2
n2(k1)(k2)n(n1k)(k1)(k2)2
=nk(k1)(k2)2(k1)(k2)20.

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.

Tsuyoshi Ito
quelle
Dies kommt der spezifischen Formulierung am nächsten. Vielen Dank, dass Sie sich damit befasst haben. Fall 3 kommt dem, was ich mir vorgestellt habe, am nächsten. Ich folge jedoch nicht der Berechnung - könnten Sie etwas erweitern?
András Salamon
@ András Salamon: Fertig.
Tsuyoshi Ito
15

ptplog4tslog2ttlog2t

log2t

p

Boaz Barak
quelle