In der Informatik bezieht sich das Clique-Problem auf einige der Probleme, die mit der Entdeckung besonderer ganzer Subgraphen ("Cliquen") in einem Graphen, d. h., Sätze von Elementen verbunden sind, wo jedes Paar von Elementen verbunden wird.

Zum Beispiel entsteht das maximale Clique-Problem in der folgenden wirklichen Einstellung. Denken Sie ein soziales Netz, wo die Scheitelpunkte des Graphen Leute vertreten, und die Ränder des Graphen gegenseitige Bekanntschaft vertreten. Um eine größte Teilmenge von Leuten zu finden, die alle einander kennen, kann man alle Teilmengen, ein Prozess systematisch untersuchen, der zu zeitraubend ist, um für soziale Netze praktisch zu sein, die mehr als einige Dutzend Menschen umfassen. Obwohl diese Suche der rohen Gewalt durch effizientere Algorithmen verbessert werden kann, nehmen alle diese Algorithmen Zeit in Anspruch, um das Problem zu beheben. Deshalb wird viel von der Theorie über das Clique-Problem dem Identifizieren von speziellen Typen des Graphen gewidmet, die effizientere Algorithmen, oder zum Herstellen der rechenbetonten Schwierigkeit des allgemeinen Problems in verschiedenen Modellen der Berechnung zulassen. Zusammen mit seinen Anwendungen in sozialen Netzen hat das Clique-Problem auch viele Anwendungen in bioinformatics und rechenbetonter Chemie.

Clique-Probleme schließen ein:

• die maximale Clique (eine Clique mit der größten Zahl von Scheitelpunkten), findend
• eine maximale Gewicht-Clique in einem belasteten Graphen, findend
• die Auflistung aller maximalen Cliquen (Cliquen, die nicht vergrößert werden können)
• das Beheben des Entscheidungsproblems der Prüfung, ob ein Graph eine Clique enthält, die größer ist als eine gegebene Größe.

Diese Probleme sind alle hart: Das Clique-Entscheidungsproblem ist NP-complete (eines von 21 NP-complete Problemen von Karp), dem Problem zu finden, dass die maximale Clique sowohl fester Parameter unnachgiebig als auch hart ist näher zu kommen, und alle maximalen Cliquen verzeichnend, Exponentialzeit verlangen kann, weil dort Graphen mit exponential vielen maximalen Cliquen bestehen. Dennoch gibt es Algorithmen für diese Probleme, die in der Exponentialzeit oder diesem Griff bestimmte mehr spezialisierte Eingangsgraphen in der polynomischen Zeit führen.

Geschichte

Obwohl ganze Subgraphen für den längeren in der Mathematik, der Begriff "Clique" und das Problem algorithmisch Schlagseite habender Cliquen studiert worden sind, kommen beide aus den Sozialwissenschaften, wo ganze Subgraphen verwendet werden, um soziale Cliquen, Gruppen von Leuten zu modellieren, die alle einander kennen. Die "Clique"-Fachsprache kommt her, und der erste Algorithmus, für das Clique-Problem zu beheben, ist der dessen, die durch die soziologische Anwendung motiviert wurden.

Seit der Arbeit von Harary und Ross haben viele andere Algorithmen für verschiedene Versionen des Clique-Problems ausgedacht. In den 1970er Jahren haben Forscher begonnen, diese Algorithmen aus dem Gesichtswinkel von der Grenzfall-Analyse zu studieren; sieh zum Beispiel, eine frühe Arbeit an der Grenzfall-Kompliziertheit des maximalen Clique-Problems. Auch in den 1970er Jahren, mit der Arbeit beginnend, und, haben Forscher begonnen, mathematische Rechtfertigung für die wahrgenommene Schwierigkeit des Clique-Problems in der Theorie der NP-Vollständigkeit zu finden, und haben Hartnäckigkeitsergebnisse verbunden. In den 1990er Jahren hat eine Durchbruch-Reihe von Papieren, die damit beginnen, und zurzeit in Hauptzeitungen berichtet, hat gezeigt, dass es nicht sogar möglich ist, dem Problem genau und effizient näher zu kommen.

Definitionen

Ein ungeleiteter Graph wird durch einen begrenzten Satz von Scheitelpunkten und eine Reihe nicht eingeordneter Paare von Scheitelpunkten gebildet, die Ränder genannt werden. Durch die Tagung, in der Algorithmus-Analyse, wird die Zahl von Scheitelpunkten im Graphen durch n angezeigt, und die Zahl von Rändern wird durch die M angezeigt. Eine Clique in einem Graphen G ist ein ganzer Subgraph von G; d. h. es ist eine Teilmenge S der solcher Scheitelpunkte, dass alle zwei Scheitelpunkte in S einen Rand in G bilden. Eine maximale Clique ist eine Clique, zu der keine Scheitelpunkte mehr hinzugefügt werden können; eine maximale Clique ist eine Clique, die die größtmögliche Zahl von Scheitelpunkten einschließt, und die Clique-Zahl ω (G) die Zahl von Scheitelpunkten in einer maximalen Clique von G ist.

Mehrere nah zusammenhängende Clique findende Probleme sind studiert worden.

• Im maximalen Clique-Problem ist der Eingang ein ungeleiteter Graph, und die Produktion ist eine maximale Clique im Graphen. Wenn es vielfache maximale Cliquen gibt, nur ein Bedürfnis sind Produktion.
• Im belasteten maximalen Clique-Problem ist der Eingang ein ungeleiteter Graph mit Gewichten auf seinen Scheitelpunkten (oder, weniger oft, Ränder), und die Produktion ist eine Clique mit dem maximalen Gesamtgewicht. Das maximale Clique-Problem ist der spezielle Fall, in dem alle Gewichte dasjenige sind.
• In der maximalen Clique, die Problem verzeichnet, ist der Eingang ein ungeleiteter Graph, und die Produktion ist eine Liste aller seiner maximalen Cliquen. Das maximale Clique-Problem kann mit als ein Unterprogramm einen Algorithmus für die maximale Clique behoben werden, die Problem verzeichnet, weil die maximale Clique unter allen maximalen Cliquen eingeschlossen werden muss.
• Im K-Clique-Problem ist der Eingang ein ungeleiteter Graph und eine Nummer k, und die Produktion ist eine Clique der Größe k, wenn man (oder, manchmal, alle Cliquen der Größe k) besteht.
• Im Clique-Entscheidungsproblem ist der Eingang ein ungeleiteter Graph und eine Nummer k, und die Produktion ist ein Wert von Boolean: Wahr, wenn der Graph eine K-Clique, und falsch sonst enthält.

Die ersten vier dieser Probleme sind alle in praktischen Anwendungen wichtig; das Clique-Entscheidungsproblem ist nicht, aber ist notwendig, um die Theorie der NP-Vollständigkeit zu Clique findenden Problemen anzuwenden.

Das Clique-Problem und das unabhängige Satz-Problem sind ergänzend: Eine Clique in G ist ein unabhängiger Satz im Ergänzungsgraphen von G und umgekehrt. Deshalb können viele rechenbetonte Ergebnisse ebenso gut auf jedes Problem angewandt werden, und einige Forschungsarbeiten unterscheiden zwischen den zwei Problemen nicht klar. Jedoch haben die zwei Probleme verschiedene Eigenschaften, wenn angewandt, auf eingeschränkte Familien von Graphen; zum Beispiel kann das Clique-Problem in der polynomischen Zeit für planare Graphen behoben werden, während das unabhängige Satz-Problem NP-hard auf planaren Graphen bleibt.

Algorithmen

Maximal gegen das Maximum

Eine maximale Clique, manchmal genannt mit der Einschließung maximal, ist eine Clique, die in eine größere Clique nicht eingeschlossen wird. Die Entdeckung einer maximalen Clique ist aufrichtig: Das Starten mit einem einzelnen Scheitelpunkt, wachsen Sie die aktuelle Clique ein Scheitelpunkt auf einmal, indem Sie über die restlichen Scheitelpunkte des Graphen wiederholen, einen Scheitelpunkt hinzufügend, wenn es mit jedem Scheitelpunkt in der aktuellen Clique und Verschrottung davon sonst verbunden wird. Dieser Algorithmus führt in O (m) Zeit. Jedoch können maximale Cliquen sehr klein sein; ein Graph kann eine Clique der Größe n−1, aber eine maximale Clique der Größe 2 enthalten. So, während ein Maximum (d. h., am größten) Clique notwendigerweise maximal ist, hält das gegenteilige nicht, und der grösste Teil algorithmischen Aufmerksamkeit wird auf das viel härtere Problem gelenkt, ein Maximum oder sonst große Clique zu finden.

Cliquen der festen Größe

Ein Algorithmus der rohen Gewalt, um zu prüfen, ob ein Graph G eine K-Scheitelpunkt-Clique enthält, und eine solche Clique zu finden, die es enthält, soll jeden Subgraphen mit mindestens k Scheitelpunkte und Kontrolle untersuchen, um zu sehen, ob es eine Clique bildet. Dieser Algorithmus nimmt O (n k) Zeit in Anspruch: Es gibt O (n) Subgraphen, um zu überprüfen, von denen jeder O (k) Ränder hat, deren Anwesenheit in G überprüft werden muss. So kann das Problem in der polynomischen Zeit behoben werden, wann auch immer k eine feste Konstante ist. Wenn k ein Teil des Eingangs zum Problem jedoch ist, ist die Zeit Exponential-.

Der einfachste nichttriviale Fall des Clique findenden Problems findet ein Dreieck in einem Graphen, oder bestimmt gleichwertig, ob der Graph ohne Dreiecke ist.

In einem Graphen mit der M Ränder kann es am grössten Teil von Θ (m) Dreiecke geben; der Grenzfall kommt vor, wenn G selbst eine Clique ist. Deshalb müssen Algorithmen, um alle Dreiecke zu verzeichnen, mindestens Ω (m) Zeit mit dem Grenzfall nehmen, und Algorithmen sind bekannt, die das fristgebunden vergleichen. Beschreiben Sie zum Beispiel einen Algorithmus, der die Scheitelpunkte in der Ordnung vom höchsten Grad bis niedrigsten sortiert und dann durch jeden Scheitelpunkt v in der sortierten Liste wiederholt, nach Dreiecken suchend, die v einschließen und keinen vorherigen Scheitelpunkt in die Liste einschließen. Um so zu tun, kennzeichnet der Algorithmus alle Nachbarn von v, durchsucht das ganze Rand-Ereignis einem Nachbar von v outputting ein Dreieck für jeden Rand, der zwei gekennzeichnete Endpunkte hat, und dann die Zeichen entfernt und v vom Graphen löscht. Da sich die Autoren zeigen, ist die Zeit für diesen Algorithmus zum arboricity des Graphen ((G)) Zeiten die Zahl von Rändern proportional, die O (M (G)) ist. Da der arboricity am grössten Teil von O (m), dieser Algorithmus Läufe rechtzeitig O (m) ist. Mehr allgemein können alle K-Scheitelpunkt-Cliquen durch einen ähnlichen Algorithmus verzeichnet werden, der proportional zur Zahl von Rand-Zeiten Zeit in Anspruch nimmt (k − 2) Nd-Macht des arboricity. Für Graphen von unveränderlichem arboricity, wie planare Graphen (oder in allgemeinen Graphen von jeder nichttrivialen gering geschlossenen Graph-Familie), nimmt dieser Algorithmus O (m) Zeit, die optimal ist, da es in der Größe des Eingangs geradlinig ist.

Wenn man nur ein einzelne Dreieck oder eine Versicherung wünscht, dass der Graph ohne Dreiecke ist, schnellere Algorithmen möglich sind. Wie bemerken, enthält der Graph ein Dreieck, wenn, und nur wenn seine Angrenzen-Matrix und das Quadrat der Angrenzen-Matrix Nichtnulleinträge in derselben Zelle enthalten; deshalb können schnelle Matrixmultiplikationstechniken wie der Algorithmus des Kupferschmieds-Winograd angewandt werden, um Dreiecke rechtzeitig O (n) zu finden, der schneller sein kann als O (m) für genug dichte Graphen. haben den O (m) Algorithmus verbessert, um Dreiecke zu O (m) durch das Verwenden schneller Matrixmultiplikation zu finden. Diese Idee, schnelle Matrixmultiplikation zu verwenden, um Dreiecke zu finden, ist auch zu Problemen erweitert worden, K-Cliquen für größere Werte von k zu finden.

Die Auflistung aller maximalen Cliquen

Durch ein Ergebnis hat jeder N-Scheitelpunkt-Graph höchstens 3 maximale Cliquen. Der Algorithmus von Bron-Kerbosch ist ein rekursives denselben Weg zurückverfolgendes Verfahren davon vermehrt eine Kandidat-Clique durch das Betrachten eines Scheitelpunkts auf einmal, entweder das Hinzufügen davon zur Kandidat-Clique oder zu einer Reihe von ausgeschlossenen Scheitelpunkten, die in der Clique nicht sein können, aber einen Nichtnachbar in der schließlichen Clique haben müssen; wie man zeigen kann, haben Varianten dieses Algorithmus Grenzfall-Laufzeit O (3). Deshalb stellt das eine mit dem Grenzfall optimale Lösung des Problems zur Verfügung, alle maximalen unabhängigen Sätze zu verzeichnen; weiter ist der Algorithmus von Bron-Kerbosch weit berichtet worden als, schneller in der Praxis zu sein, als seine Alternativen.

Wie sich gezeigt hat, ist es auch möglich, alle maximalen Cliquen in einem Graphen in einer Zeitdauer zu verzeichnen, die Polynom pro erzeugte Clique ist. Ein Algorithmus solcher so ist ihriger, in dem die Laufzeit von der Produktionsgröße abhängt, bekannt wie ein mit der Produktion empfindlicher Algorithmus. Ihr Algorithmus basiert auf den folgenden zwei Beobachtungen, die maximalen Cliquen des gegebenen Graphen G zu den maximalen Cliquen eines Graphen G \v gebildet durch das Entfernen eines willkürlichen Scheitelpunkts v von G verbindend:

• Für jede maximale Clique C G \v setzt entweder C fort, eine maximale Clique in G zu bilden, oder C  {v} bildet eine maximale Clique in G. Deshalb hat G mindestens so viele maximale Cliquen wie G \v tun.
• Jede maximale Clique in G, der v nicht enthält, ist eine maximale Clique in G \v, und jede maximale Clique in G, der wirklich v enthält, kann von einer maximalen Clique C in G \v gebildet werden, indem sie v beiträgt und die Nichtnachbarn von v von C entfernt.

Mit diesen Beobachtungen können sie alle maximalen Cliquen in G durch einen rekursiven Algorithmus dass, für jede maximale Clique C in G \v, Produktionen C und die gebildete Clique erzeugen, indem sie v zu C beitragen und die Nichtnachbarn von v entfernen. Jedoch können einige Cliquen von G auf diese Weise von mehr als einer Elternteilclique von G \v erzeugt werden, so beseitigen sie Duplikate durch outputting eine Clique in G nur, wenn sein Elternteil in G \v unter allen möglichen Elternteilcliquen lexikografisch maximal ist. Auf der Grundlage von diesem Grundsatz zeigen sie, dass alle maximalen Cliquen in G rechtzeitig O (mn) pro Clique erzeugt werden können, wo M die Zahl von Rändern in G ist und n die Zahl von Scheitelpunkten ist; verbessern Sie das zu O (ma) pro Clique, wo des arboricity des gegebenen Graphen zu sein. stellen Sie einen alternativen mit der Produktion empfindlichen Algorithmus zur Verfügung, der auf der schnellen Matrixmultiplikation gestützt ist und zeigen Sie, dass es sogar möglich ist, alle maximalen Cliquen in der lexikografischen Ordnung mit der polynomischen Verzögerung pro Clique zu verzeichnen, obwohl die Rückseite dieser Ordnung NP-hard ist, um zu erzeugen.

Auf der Grundlage von diesem Ergebnis ist es möglich, alle maximalen Cliquen in der polynomischen Zeit für Familien von Graphen zu verzeichnen, in denen die Zahl von Cliquen polynomisch begrenzt wird. Diese Familien schließen chordal Graphen ein, vollenden Graphen, Graphen ohne Dreiecke, Zwischenraum-Graphen, Graphen von begrenztem boxicity und planare Graphen. Insbesondere die planaren Graphen, und mehr allgemein, jede Familie von Graphen, die beide spärlich ist (mehrere Ränder höchstens eine Konstante Zeiten die Zahl von Scheitelpunkten zu haben), und geschlossen unter der Operation, Subgraphen zu nehmen, haben O (n) Cliquen, an der unveränderlichsten Größe, die in der geradlinigen Zeit verzeichnet werden kann.

Die Entdeckung maximaler Cliquen in willkürlichen Graphen

Es ist möglich, die maximale Clique oder die Clique-Zahl, von einem willkürlichen N-Scheitelpunkt-Graphen rechtzeitig O (3) = O (1.4422) durch das Verwenden von einem der Algorithmen zu finden, die oben beschrieben sind, um alle maximalen Cliquen im Graphen und das Zurückbringen des größten zu verzeichnen. Jedoch für diese Variante des Clique-Problems sind bessere Grenzfall-Zeitgrenzen möglich. Der Algorithmus dessen behebt dieses Problem rechtzeitig O (2) = O (1.2599); es ist ein rekursives denselben Weg zurückverfolgendes Schema, das diesem des Algorithmus von Bron-Kerbosch ähnlich ist, aber ist im Stande, einige rekursive Anrufe zu beseitigen, wenn es gezeigt werden kann, dass, wie man versichert, eine andere Kombination von im Anruf nicht verwendeten Scheitelpunkten zu einer Lösung mindestens als gut führt. verbessert das zu O (2) = O (1.2346). verbessert das zu O (2) = O (1.2108) ist Zeit, auf Kosten des größeren Raumgebrauchs, durch ein ähnliches denselben Weg zurückverfolgendes Schema mit einer mehr komplizierten Fall-Analyse, zusammen mit einer dynamischen Programmiertechnik, in der die optimale Lösung für alle kleinen verbundenen Subgraphen des Ergänzungsgraphen und dieser partials Lösungen vorgeschätzt wird, an die Abkürzung das Zurückverfolgen recursion gewöhnt. Der schnellste Algorithmus bekannt ist heute wegen der Läufe rechtzeitig O (2) = O (1.1888).

Es hat auch umfassende Forschung über heuristische Algorithmen gegeben, um maximale Clique-Probleme ohne Grenzfall-Laufzeitgarantien zu beheben, die auf Methoden einschließlich Zweigs und gebundener, lokaler Suche, gieriger Algorithmen und Einschränkungsprogrammierung gestützt sind. Sonderrechenmethodiken, um Cliquen zu finden, schließen DNA-Computerwissenschaft und adiabatische Quant-Berechnung ein. Das maximale Clique-Problem war das Thema einer Durchführungsherausforderung, die durch DIMACS in 1992-1993 gesponsert ist, und eine Sammlung von Graphen, die als Abrisspunkte für die Herausforderung verwendet sind, ist öffentlich verfügbar.

Spezielle Klassen von Graphen

Planare Graphen und andere Familien von spärlichen Graphen, sind oben besprochen worden: Sie haben geradlinig viele maximale Cliquen der begrenzten Größe, die in der geradlinigen Zeit verzeichnet werden kann. Insbesondere für planare Graphen kann jede Clique höchstens vier Scheitelpunkte durch den Lehrsatz von Kuratowski haben.

Vollkommene Graphen werden durch die Eigenschaften definiert, dass ihre Clique-Zahl ihrer chromatischen Zahl gleichkommt, und dass diese Gleichheit auch in jedem ihrer veranlassten Subgraphen hält. Für vollkommene Graphen ist es möglich, eine maximale Clique in der polynomischen Zeit mit einem auf der halbbestimmten Programmierung gestützten Algorithmus zu finden.

Jedoch ist diese Methode kompliziert und nichtkombinatorisch, und hat sich spezialisiert Clique findende Algorithmen sind für viele Unterklassen von vollkommenen Graphen entwickelt worden. In den Ergänzungsgraphen von zweiteiligen Graphen erlaubt der Lehrsatz von König dem maximalen Clique-Problem, mit Techniken für das Zusammenbringen gelöst zu werden. In einer anderen Klasse von vollkommenen Graphen, den Versetzungsgraphen, ist eine maximale Clique eine längste abnehmende Subfolge der Versetzung, die den Graphen definiert, und kann mit bekannten Algorithmen für das längste abnehmende Subfolge-Problem gefunden werden. In chordal Graphen sind die maximalen Cliquen eine Teilmenge der n als ein Teil einer Beseitigungseinrichtung gebildeten Cliquen.

In einigen Fällen können diese Algorithmen zu anderem erweitert, Klassen von Graphen ebenso nichtvollkommen werden: Zum Beispiel, in einem Kreisgraphen, ist die Nachbarschaft jedes Scheitelpunkts ein Versetzungsgraph, so kann eine maximale Clique in einem Kreisgraphen gefunden werden, indem sie den Versetzungsgraph-Algorithmus auf jede Nachbarschaft anwendet. Ähnlich in einem Einheitsplattengraphen (mit einer bekannten geometrischen Darstellung) gibt es einen polynomischen Zeitalgorithmus für maximale Cliquen, die auf dem Wenden an den Algorithmus für Ergänzungen von zweiteiligen Graphen zur geteilten Nachbarschaft von Paaren von Scheitelpunkten gestützt sind.

Das algorithmische Problem, eine maximale Clique in einem zufälligen Graphen angezogen vom Erdős-Rényi Modell zu finden (in dem jeder Rand mit der Wahrscheinlichkeit 1/2 unabhängig von den anderen Rändern erscheint) wurde dadurch angedeutet. Obwohl die Clique-Zahl solcher Graphen sehr 2 logn nah ist, finden einfache gierige Algorithmen sowie hoch entwickeltere randomized Annäherungstechniken nur Cliquen mit der Größe logn, und die Zahl von maximalen Cliquen in solchen Graphen ist mit der hohen in logn Exponential-Wahrscheinlichkeit das Verhindern einer polynomischen Zeitlösung, die sie alle verzeichnet. Wegen der Schwierigkeit dieses Problems haben mehrere Autoren Varianten des Problems untersucht, in dem der zufällige Graph durch das Hinzufügen einer großen Clique der zu n proportionalen Größe vermehrt wird. Es ist möglich, diese verborgene Clique mit der hohen Wahrscheinlichkeit in der polynomischen Zeit, mit entweder geisterhaften Methoden oder halbbestimmter Programmierung zu finden.

Annäherungsalgorithmen

Mehrere Autoren haben Annäherungsalgorithmen gedacht, die versuchen, eine Clique oder unabhängigen Satz zu finden, der, obwohl nicht maximal, Größe als in der Nähe vom Maximum hat, wie in der polynomischen Zeit gefunden werden kann.

Obwohl sich viel von dieser Arbeit auf unabhängige Sätze in spärlichen Graphen konzentriert hat, ein Fall, der Sinn für das Ergänzungsclique-Problem nicht hat, hat es auch Arbeit an Annäherungsalgorithmen gegeben, die solche sparsity Annahmen nicht verwenden.

beschreibt einen polynomischen Zeitalgorithmus, der eine Clique der Größe Ω findet ((, loggen Sie N/log-Klotz n)) in jedem Graphen, der Clique-Zahl Ω (n/logn) für jeden unveränderlichen k hat. Durch das Kombinieren dieses Algorithmus, um Cliquen in Graphen mit Clique-Zahlen zwischen n/log n und n/logn mit einem verschiedenen Algorithmus zu finden, Cliquen in Graphen mit höheren Clique-Zahlen, und die Auswahl einer Zwei-Scheitelpunkte-Clique zu finden, wenn beide Algorithmen scheitern, irgendetwas zu finden, stellt Feige einen Annäherungsalgorithmus zur Verfügung, der eine Clique mit mehreren Scheitelpunkten innerhalb eines Faktors von O findet (n (Klotz loggen n)/logn) des Maximums. Obwohl das Annäherungsverhältnis dieses Algorithmus schwach ist, ist es bis heute am besten bekannt, und die Ergebnisse auf der Härte der Annäherung, die unten beschrieben ist, weisen darauf hin, dass es keinen Annäherungsalgorithmus mit einem bedeutsam weniger als geradlinigen Annäherungsverhältnis geben kann.

Niedrigere Grenzen

NP-Vollständigkeit

Das Clique-Entscheidungsproblem ist NP-complete. Es war eines der ursprünglichen 21 Probleme von Richard Karp gezeigt NP-complete in seiner 1972-Zeitung "Reducibility Unter Kombinatorischen Problemen". Dieses Problem wurde auch in der Zeitung von Stephen Cook erwähnt, die die Theorie von NP-complete Problemen einführt. So ist das Problem, eine maximale Clique zu finden, NP-hard: Wenn man es lösen konnte, konnte man auch das Entscheidungsproblem beheben, indem man die Größe der maximalen Clique zum Größe-Parameter verglichen hat, der als Eingang im Entscheidungsproblem gegeben ist.

Der NP-Vollständigkeitsbeweis von Karp ist vieleine Verminderung vom Problem von Boolean satisfiability für Formeln in der verbindenden normalen Form, die NP-complete im Lehrsatz des Kochs-Levin bewiesen wurde. Von einer gegebenen CNF Formel bildet Karp einen Graphen, der einen Scheitelpunkt für jedes Paar hat (v, c), wo v eine Variable oder seine Ablehnung ist und c eine Klausel in der Formel ist, die v enthält. Scheitelpunkte werden durch einen Rand verbunden, wenn sie vereinbare variable Anweisungen für verschiedene Klauseln vertreten: D. h. es gibt einen Rand von (v, c) dazu (u, d), wann auch immer c  d und u und v nicht jeder die Ablehnungen der anderen sind. Wenn k die Zahl von Klauseln in der CNF Formel anzeigt, dann vertreten die K-Scheitelpunkt-Cliquen in diesem Graphen Weisen, Wahrheitswerte einigen seiner Variablen zuzuteilen, um die Formel zu befriedigen; deshalb ist die Formel satisfiable, wenn, und nur wenn eine K-Scheitelpunkt-Clique besteht.

Einige NP-complete Probleme (wie das Handlungsreisender-Problem in planaren Graphen) können rechtzeitig behoben werden, der in einer subgeradlinigen Funktion des Eingangsgröße-Parameters n Exponential-ist.

Jedoch, wie beschreiben, ist es unwahrscheinlich, dass solche Grenzen für das Clique-Problem in willkürlichen Graphen bestehen, weil sie ähnlich Subexponentialgrenzen für viele NP-complete andere Standardprobleme einbeziehen würden.

Stromkreis-Kompliziertheit

Die rechenbetonte Schwierigkeit des Clique-Problems hat es dazu gebracht, verwendet zu werden, um mehrere niedrigere Grenzen in der Stromkreis-Kompliziertheit zu beweisen. Weil die Existenz einer Clique einer gegebenen Größe ein Eintönigkeitsgraph-Eigentum ist (wenn eine Clique in einem gegebenen Graphen besteht, wird es in jedem Supergraphen bestehen) dort muss ein Eintönigkeitsstromkreis, mit nur und Tore und oder Tore bestehen, um das Clique-Entscheidungsproblem für eine gegebene befestigte Clique-Größe zu beheben. Jedoch, wie man beweisen kann, ist die Größe dieser Stromkreise eine superpolynomische Funktion der Zahl von Scheitelpunkten und der Clique-Größe, die in der Würfel-Wurzel der Zahl von Scheitelpunkten Exponential-ist. Selbst wenn eine kleine Zahl von NICHT Toren erlaubt wird, bleibt die Kompliziertheit superpolynomisch. Zusätzlich muss die Tiefe eines Eintönigkeitsstromkreises für das Clique-Problem mit Toren des begrenzten Anhängers - darin mindestens ein Polynom in der Clique-Größe sein.

Entscheidungsbaum-Kompliziertheit

Die (deterministische) Entscheidungsbaum-Kompliziertheit, ein Graph-Eigentum zu bestimmen, ist die Zahl von Fragen der Form "Ist dort ein Rand zwischen Scheitelpunkt u und Scheitelpunkt v?" darauf muss im Grenzfall geantwortet werden, um zu bestimmen, ob ein Graph ein besonderes Eigentum hat. D. h. es ist die minimale Höhe eines boolean Entscheidungsbaums für das Problem. Da es am grössten Teil von n gibt (n − 1)/2 mögliche Fragen, gefragt zu werden, kann jedes Graph-Eigentum mit n bestimmt werden (n − 1)/2-Fragen. Es ist auch möglich, zufällig und Quant-Entscheidungsbaum-Kompliziertheit eines Eigentums, die erwartete Zahl von Fragen zu definieren (für einen Grenzfall-Eingang), auf den randomized- oder Quant-Algorithmus geantwortet haben muss, um richtig zu bestimmen, ob der gegebene Graph das Eigentum hat.

Weil das Eigentum, eine Clique zu enthalten, ein Eintönigkeitseigentum ist (das Hinzufügen, dass ein Rand nur mehr Cliquen veranlassen kann, innerhalb des Graphen, nicht weniger zu bestehen), wird es durch die Aanderaa-Karp-Rosenberg-Vermutung bedeckt, die feststellt, dass die deterministische Entscheidungsbaum-Kompliziertheit, jedes nichttriviale Eintönigkeitsgraph-Eigentum zu bestimmen, genau n ist (n − 1)/2. Für deterministische Entscheidungsbäume, wie man zeigte, hatte das Eigentum, eine K-Clique (2  k  n) zu enthalten, Entscheidungsbaum-Kompliziertheit genau n (n − 1)/2 dadurch. Deterministische Entscheidungsbäume verlangen auch, dass Exponentialgröße Cliquen oder große polynomische Größe entdeckt, um Cliquen der begrenzten Größe zu entdecken.

Die Aanderaa-Karp-Rosenberg-Vermutung stellt auch fest, dass die randomized Entscheidungsbaum-Kompliziertheit von nichttrivialen Eintönigkeitsfunktionen Θ (n) ist. Die Vermutung wird für das Eigentum aufgelöst, eine K-Clique zu enthalten (2  k  n), da, wie man bekannt, es randomized Entscheidungsbaum-Kompliziertheit Θ (n) hat. Für Quant-Entscheidungsbäume ist das tiefer gebundene am besten bekannte Ω (n), aber kein zusammenpassender Algorithmus ist für den Fall von k  3 bekannt.

Hartnäckigkeit des festen Parameters

Parametrisierte Kompliziertheit ist die mit der Kompliziertheit theoretische Studie von Problemen, die mit einem kleinen Parameter der ganzen Zahl k natürlich ausgestattet werden, und für den das Problem schwieriger als k Zunahmen, wie Entdeckung von K-Cliquen in Graphen wird. Wie man sagt, ist ein Problem lenksamer fester Parameter, wenn es einen Algorithmus gibt, um es auf Eingängen der Größe n rechtzeitig f (k) n zu lösen; d. h. wenn es in der polynomischen Zeit für einen festen Wert von k und außerdem gelöst werden kann, wenn die Hochzahl des Polynoms von k nicht abhängt.

Für das Clique-Problem hat der Suchalgorithmus der rohen Gewalt Laufzeit O (nk), und obwohl es durch die schnelle Matrixmultiplikation verbessert werden kann, hat die Laufzeit noch eine Hochzahl, die in k geradlinig ist. So, obwohl die Laufzeit bekannter Algorithmen für das Clique-Problem Polynom für irgendwelchen ist, hat k befestigt, diese Algorithmen genügen für die Lenkbarkeit des festen Parameters nicht. definiert eine Hierarchie von parametrisierten Problemen, die W Hierarchie, die sie vermutet haben, hatte festen Parameter lenksame Algorithmen nicht; sie haben bewiesen, dass unabhängiger Satz (oder, gleichwertig, Clique) für das erste Niveau dieser Hierarchie, W [1] hart ist. So, gemäß ihrer Vermutung, ist Clique nicht lenksamer fester Parameter. Außerdem schafft dieses Ergebnis die Grundlage für Beweise von W [1] - Härte von vielen anderen Problemen, und dient so als eine Entsprechung des Lehrsatzes des Kochs-Levin für die parametrisierte Kompliziertheit.

gezeigt, dass das Clique-Problem rechtzeitig nicht behoben werden kann, wenn die Exponentialzeithypothese nicht scheitert.

Obwohl die Probleme, maximale Cliquen zu verzeichnen oder maximale Cliquen zu finden, kaum fester Parameter sein werden, der mit dem Parameter k lenksam ist, können sie für andere Rahmen der Beispiel-Kompliziertheit lenksamer fester Parameter sein. Zum Beispiel, wie man bekannt, sind beide Probleme lenksamer wenn parametrisierter fester Parameter durch die Entartung des Eingangsgraphen.

Härte der Annäherung

Die rechenbetonte Kompliziertheit, dem Clique-Problem näher zu kommen, ist seit langem studiert worden; zum Beispiel, beobachtet, dass wegen der Tatsache, dass die Clique-Zahl kleine Werte der ganzen Zahl übernimmt und NP-hard ist, um zu rechnen, es kein völlig polynomisch-maliges Annäherungsschema haben kann. Jedoch, war ein wenig mehr bekannt bis zum Anfang der 1990er Jahre, als mehrere Autoren begonnen haben, Verbindungen zwischen der Annäherung von maximalen Cliquen und probabilistically checkable Beweise zu machen, und hat diese Verbindungen verwendet, um Härte von Annäherungsergebnissen für das maximale Clique-Problem zu beweisen.

Nach vielen Verbesserungen zu diesen Ergebnissen ist es jetzt bekannt, dass, wenn P = NP, es keinen polynomischen Zeitalgorithmus nicht geben kann, der der maximalen Clique zu innerhalb eines Faktors besser näher kommt als O (n), für jeden ε> 0.

Die raue Idee von diesen Inapproximability-Ergebnissen ist, einen Graphen zu bilden, der einen probabilistically checkable Probesystem für ein NP-complete Problem wie Satisfiability vertritt. Ein Probesystem dieses Typs wird von einer Familie von Probeschnuren (Folgen von Bit) und Probekontrolleure definiert: Algorithmen, die, nach einem polynomischen Betrag der Berechnung über ein gegebenes Beispiel von Satisfiability, eine kleine Zahl zufällig gewählter Bit der Probeschnur und auf der Grundlage von dieser Überprüfung untersuchen entweder es erklären, ein gültiger Beweis zu sein oder es zu erklären, ungültig zu sein. Falschen Negativen wird nicht erlaubt: Wie man immer erklären muss, ist ein gültiger Beweis gültig, aber, wie man erklären kann, ist ein ungültiger Beweis so lange die Wahrscheinlichkeit gültig, dass ein Kontrolleur einen Fehler dieses Typs macht, ist niedrig. Um einen probabilistically checkable Probesystem in ein Clique-Problem umzugestalten, bildet man einen Graphen, in dem die Scheitelpunkte alle möglichen Weisen vertreten, wie ein Probekontrolleur eine Folge von Probeschnur-Bit lesen und damit enden konnte, den Beweis zu akzeptieren. Zwei Scheitelpunkte werden durch einen Rand verbunden, wann auch immer sich die zwei Probekontrolleur-Läufe, die sie beschreiben, über die Werte der Probeschnur-Bit einigen, die sie beide untersuchen. Die maximalen Cliquen in diesem Graphen bestehen aus den akzeptierenden Probekontrolleur-Läufen für eine einzelne Probeschnur, und eine dieser Cliquen ist groß, wenn, und nur wenn dort eine Probeschnur besteht, die viele Probekontrolleure akzeptieren. Wenn das ursprüngliche Beispiel von Satisfiability satisfiable ist, wird es eine große Clique geben, die durch eine gültige Probeschnur für dieses Beispiel definiert ist, aber wenn das ursprüngliche Beispiel nicht satisfiable ist, dann sind alle Probeschnuren ungültig, jede Probeschnur hat nur eine kleine Zahl von Kontrolleuren, die es irrtümlicherweise akzeptieren, und alle Cliquen klein sind. Deshalb, wenn man in der polynomischen Zeit zwischen Graphen unterscheiden konnte, die große Cliquen und Graphen haben, in denen alle Cliquen klein sind, konnte man diese Fähigkeit verwenden, die Graphen zu unterscheiden, die von satisfiable und unsatisfiable Beispielen des Problems von Satisfiability erzeugt sind, nicht möglich wenn P = NP. Eine genaue polynomisch-malige Annäherung an das Clique-Problem würde diesen zwei Sätzen von Graphen erlauben, von einander bemerkenswert zu sein, und ist deshalb auch unmöglich.

Referenzen