Ist das K-Clique-Problem NP-vollständig?

In diesem Wikipedia-Artikel über das Cliquenproblem in der Graphentheorie heißt es am Anfang, dass das Problem, eine Clique der Größe K in einem Graphen G zu finden, NP-vollständig ist:

Cliquen wurden auch in der Informatik untersucht: Es wurde untersucht, ob es eine Clique einer bestimmten Größe in einem Graphen gibt (das Cliquenproblem), aber trotz dieses Härteergebnisses wurden viele Algorithmen zum Finden von Cliquen untersucht.

Aber in diesem anderen Wikipedia-Artikel über das Clique-Problem in CS heißt es, dass es das Problem für eine feste Größe löst. K ist ein Problem in P, es kann in polynomialer Zeit brutal erzwungen werden.

Ein Brute-Force-Algorithmus, um zu testen, ob ein Graph G eine k-Vertex-Clique enthält, und um eine solche Clique zu finden, besteht darin, jeden Subgraphen mit mindestens k Vertices zu untersuchen und zu prüfen, ob er eine Clique bildet. Dieser Algorithmus benötigt Zeit O (n ^ kk ^ 2): Es müssen O (n ^ k) Teilgraphen überprüft werden, von denen jeder O (k ^ 2) Kanten aufweist, deren Vorhandensein in G überprüft werden muss. Somit kann das Problem in Polynomzeit gelöst werden, wenn k eine feste Konstante ist. Wenn k Teil der Eingabe für das Problem ist, ist die Zeit jedoch exponentiell.

Fehlt mir hier etwas? Vielleicht ein Unterschied in der Formulierung des Problems? Und was bedeutet der letzte Satz: "Wenn k Teil der Eingabe für das Problem ist, ist die Zeit jedoch exponentiell." Warum gibt es einen Unterschied, wenn k Teil der Eingabe für das Problem ist?

Meine Idee ist es, eine Clique der Größe k in einem Graphen G zu finden, indem wir zuerst eine Teilmenge der Größe k von Knoten aus G auswählen und testen, ob sie alle mit den anderen Knoten in Beziehung stehen, was in konstanter Weise geschehen kann Zeit. Und wiederholen Sie dies, bis wir eine Clique der Größe k haben. Die Anzahl der Mengen von k Knoten, die wir aus G auswählen können, ist n! / k! * (nk) !.

Ich möchte nur erläutern, worauf @Lamine hingewiesen hat: Wenn Teil der Eingabe ist, kann k so groß sein wie $k$$k$ , in welchem ​​Fall die Anzahl der potentiellen Cliquensätze ($\frac{n}{2}$das ist mindestens($\binom{n}{\frac{n}{2}}$ . Daher würde Ihr naiver Algorithmus2ndauern$\left( \frac{n}{\frac{n}{2}} \right)^{\frac{n}{2}}$ die in der Eingangslänge|eindeutig exponentiell ist x| +| k| =n+logn. Die parametrisierte VersionG(n,k),in der wir nachk-Klassen in einemn-Vertex-Graphen suchen, erfasst die Härte des Problems in seiner allgemeinsten Form, dakTeil der Eingabe ist. Daher würde ein Mehrfachzeitalgorithmus fürG(n,k)auch einen Mehrfachzeitalgorithmus für jedes spezifischekimplizieren.$2^{\frac{n}{2}}$$|x|+|k|=n+\log n$$G(n,k)$$k$$n$$k$$G(n,k)$$k$