Cliquenproblem - Clique problem

Der Brute-Force-Algorithmus findet eine 4-Clique in diesem 7-Scheitelpunkt-Graphen (dem Komplement des 7-Scheitelpunkt- Pfadgraphen ), indem er systematisch alle C (7,4) = 35 4-Scheitel-Untergraphen auf Vollständigkeit überprüft .

In der Informatik ist das Cliquenproblem das Rechenproblem, Cliquen (Teilmengen von Knoten, die alle nebeneinander liegen, auch vollständige Teilgraphen genannt ) in einem Graphen zu finden . Es hat verschiedene Formulierungen, je nachdem, welche Cliquen und welche Informationen über die Cliquen gefunden werden sollen. Gängige Formulierungen des Cliquenproblems umfassen das Finden einer maximalen Clique (eine Clique mit der größtmöglichen Anzahl von Knoten), das Finden einer Clique mit maximalem Gewicht in einem gewichteten Graphen, das Auflisten aller maximalen Cliquen (Cliquen, die nicht vergrößert werden können) und das Lösen des Entscheidungsproblems um zu testen, ob ein Graph eine Clique enthält, die größer als eine gegebene Größe ist.

Das Cliquenproblem tritt in der folgenden realen Umgebung auf. Stellen Sie sich ein soziales Netzwerk vor , in dem die Scheitelpunkte des Diagramms Personen darstellen und die Kanten des Diagramms gegenseitige Bekanntschaften darstellen. Dann stellt eine Clique eine Teilmenge von Menschen dar, die sich alle kennen, und Algorithmen zum Auffinden von Cliquen können verwendet werden, um diese Gruppen gemeinsamer Freunde zu entdecken. Neben seinen Anwendungen in sozialen Netzwerken hat das Cliquenproblem auch viele Anwendungen in der Bioinformatik und Computerchemie .

Die meisten Versionen des Cliquenproblems sind schwer. Das Cliquenentscheidungsproblem ist NP-vollständig (eines von Karps 21 NP-vollständigen Problemen ). Das Problem, die maximale Clique zu finden, ist sowohl hartnäckig als auch schwer zu nähern . Und das Auflisten aller maximalen Cliquen kann eine exponentielle Zeit erfordern, da es Graphen mit exponentiell vielen maximalen Cliquen gibt. Daher widmet sich ein Großteil der Theorie des Cliquenproblems der Identifizierung spezieller Typen von Graphen, die effizientere Algorithmen zulassen, oder der Ermittlung der Rechenschwierigkeiten des allgemeinen Problems in verschiedenen Rechenmodellen.

Um eine maximale Clique zu finden, kann man alle Teilmengen systematisch inspizieren, aber diese Art der Brute-Force-Suche ist zu zeitaufwendig, um für Netzwerke mit mehr als einigen Dutzend Knoten praktikabel zu sein. Obwohl für dieses Problem kein Polynomialzeitalgorithmus bekannt ist, sind effizientere Algorithmen als die Brute-Force-Suche bekannt. Zum Beispiel kann der Bron-Kerbosch-Algorithmus verwendet werden, um alle maximalen Cliquen in der Worst-Case-Optimalzeit aufzulisten , und es ist auch möglich, sie in polynomieller Zeit pro Clique aufzulisten.

Geschichte und Anwendungen

Das Studium vollständiger Teilgraphen in der Mathematik geht der "Clique"-Terminologie voraus. Vollständige Teilgraphen tauchen beispielsweise schon früh in der mathematischen Literatur in der graphentheoretischen Neuformulierung der Ramsey-Theorie von Erdős & Szekeres (1935) auf . Aber der Begriff "Clique" und das Problem der algorithmischen Auflistung von Cliquen stammen beide aus den Sozialwissenschaften, wo vollständige Untergraphen verwendet werden, um soziale Cliquen , Gruppen von Menschen, die sich alle kennen , zu modellieren . Luce & Perry (1949) verwendeten Graphen, um soziale Netzwerke zu modellieren, und passten die sozialwissenschaftliche Terminologie an die Graphentheorie an. Sie waren die ersten, die komplette Teilgraphen "Cliquen" nannten. Der erste Algorithmus zur Lösung des Cliquenproblems ist der von Harary & Ross (1957) , die durch die soziologische Anwendung motiviert wurden. Sozialwissenschaftliche Forscher haben auch verschiedene andere Arten von Cliquen und maximale Cliquen in sozialen Netzwerken definiert, "kohäsive Untergruppen" von Personen oder Akteuren im Netzwerk, die alle eine von mehreren verschiedenen Arten von Konnektivitätsbeziehungen teilen. Viele dieser verallgemeinerten Vorstellungen von Cliquen können auch gefunden werden, indem man einen ungerichteten Graphen konstruiert, dessen Kanten verwandte Paare von Akteuren aus dem sozialen Netzwerk darstellen, und dann einen Algorithmus für das Cliquenproblem auf diesen Graphen anwendet.

Seit der Arbeit von Harary und Ross haben viele andere Algorithmen für verschiedene Versionen des Cliquenproblems entwickelt. In den 1970er Jahren begannen Forscher, diese Algorithmen unter dem Gesichtspunkt der Worst-Case-Analyse zu untersuchen . Siehe zum Beispiel Tarjan & Trojanowski (1977) , eine frühe Arbeit über die Worst-Case-Komplexität des Maximum-Clique-Problems. Ebenfalls in den 1970er Jahren, beginnend mit der Arbeit von Cook (1971) und Karp (1972) , begannen die Forscher, die Theorie der NP-Vollständigkeit und die damit verbundenen Widerspenstigkeitsergebnisse zu verwenden, um eine mathematische Erklärung für die wahrgenommene Schwierigkeit des Cliquenproblems zu liefern. In den 1990er Jahren begann eine bahnbrechende Reihe von Arbeiten, beginnend mit Feige et al. (1991) und in der New York Times berichtet , zeigten, dass es (unter der Annahme von P NP ) nicht einmal möglich ist, das Problem genau und effizient zu approximieren .

Cliquenfindungsalgorithmen werden in der Chemie verwendet , um Chemikalien zu finden, die einer Zielstruktur entsprechen, und um das molekulare Andocken und die Bindungsstellen chemischer Reaktionen zu modellieren . Sie können auch verwendet werden, um ähnliche Strukturen in verschiedenen Molekülen zu finden. Bei diesen Anwendungen bildet man einen Graphen, in dem jeder Scheitelpunkt ein übereinstimmendes Atompaar repräsentiert, eines aus jedem von zwei Molekülen. Zwei Scheitelpunkte werden durch eine Kante verbunden, wenn die Übereinstimmungen, die sie darstellen, miteinander kompatibel sind. Kompatibilität kann beispielsweise bedeuten, dass die Abstände zwischen den Atomen innerhalb der beiden Moleküle innerhalb einer bestimmten Toleranz ungefähr gleich sind. Eine Clique in diesem Diagramm stellt eine Menge von übereinstimmenden Atompaaren dar, in denen alle Übereinstimmungen miteinander kompatibel sind. Ein Spezialfall dieser Methode ist die Verwendung des modularen Produkts von Graphen , um das Problem des Findens des maximalen gemeinsamen induzierten Teilgraphen zweier Graphen auf das Problem des Findens einer maximalen Clique in ihrem Produkt zu reduzieren .

Bei der automatischen Testmustergenerierung kann das Auffinden von Cliquen helfen, die Größe eines Testsatzes zu begrenzen. In der Bioinformatik , Clique Findungsalgorithmen verwendet wurde abzuleiten evolutionäre Bäume , vorherzusagen , Proteinstrukturen und eng zusammenwirkenden Cluster von Proteinen zu finden. Die Auflistung der Cliquen in einem Abhängigkeitsgraphen ist ein wichtiger Schritt bei der Analyse bestimmter Zufallsprozesse. In der Mathematik wurde Kellers Vermutung über die Face-to-Face-Kachelung von Hyperwürfeln von Lagarias & Shor (1992) widerlegt , die einen Cliquenfindungsalgorithmus für einen zugehörigen Graphen verwendeten, um ein Gegenbeispiel zu finden.

Definitionen

Der gezeigte Graph hat eine maximale Clique, das Dreieck {1,2,5}, und vier weitere maximale Cliquen, die Paare {2,3}, {3,4}, {4,5} und {4,6} .

Ein ungerichteter Graph besteht aus einer endlichen Menge von Ecken und einer Menge von ungeordneten Paaren von Ecken, die Kanten genannt werden . Konventionell wird bei der Algorithmusanalyse die Anzahl der Scheitelpunkte im Graphen mit $n bezeichnet$ und die Anzahl der Kanten wird mit $m bezeichnet$ . Eine Clique in einem Graphen $G$ ist ein vollständiger Teilgraph von $G$ . Das heißt, es ist eine Teilmenge $K$ der Scheitelpunkte, so dass alle zwei Scheitelpunkte in $K$ die beiden Endpunkte einer Kante in $G sind$ . Eine maximale Clique ist eine Clique, der keine weiteren Scheitelpunkte hinzugefügt werden können. Für jede Ecke $v$ , die nicht Teil einer maximalen Clique ist, muss es eine andere Ecke $w geben$ , die sich in der Clique befindet und nicht an $v$ angrenzt , wodurch verhindert wird, dass $v$ zur Clique hinzugefügt wird. Eine maximale Clique ist eine Clique, die die größtmögliche Anzahl von Scheitelpunkten enthält. Die Clique Zahl $ω (G)$ ist die Anzahl der Scheitelpunkte in einer maximalen Gruppe von $G$ .

Mehrere eng verwandte Cliquenfindungsprobleme wurden untersucht.

Beim Maximum-Clique-Problem ist die Eingabe ein ungerichteter Graph und die Ausgabe eine maximale Clique im Graphen. Bei mehreren maximalen Cliquen kann eine davon beliebig gewählt werden.
Beim Problem der gewichteten maximalen Clique ist die Eingabe ein ungerichteter Graph mit Gewichten auf seinen Scheitelpunkten (oder seltener Kanten) und die Ausgabe ist eine Clique mit maximalem Gesamtgewicht. Das Maximum-Clique-Problem ist der Spezialfall, in dem alle Gewichte gleich sind. Neben dem Problem der Optimierung der Summe von Gewichten wurden auch andere kompliziertere Zweikriteriumsoptimierungsprobleme untersucht.
Beim maximalen Cliquen-Auflistungsproblem ist die Eingabe ein ungerichteter Graph und die Ausgabe eine Liste aller ihrer maximalen Cliquen. Das Maximum-Clique-Problem kann unter Verwendung eines Algorithmus für das Maximum-Clique-Auflistungsproblem als Unterprogramm gelöst werden, da die Maximum-Clique unter allen maximalen Cliquen enthalten sein muss.
Beim $k-$ Clique-Problem ist die Eingabe ein ungerichteter Graph und eine Zahl $k$ . Die Ausgabe ist eine Clique mit $k$ Knoten, falls vorhanden, oder ein spezieller Wert, der andeutet, dass es sonst keine $k$ -Clique gibt. In einigen Variationen dieses Problems sollte die Ausgabe alle Cliquen der Größe $k auflisten$ .
Beim Clique-Entscheidungsproblem ist die Eingabe ein ungerichteter Graph und eine Zahl $k$ , und die Ausgabe ist ein boolescher Wert : wahr, wenn der Graph eine $k-$ Clique enthält , andernfalls falsch.

Die ersten vier dieser Probleme sind alle in praktischen Anwendungen wichtig. Das Cliquenentscheidungsproblem hat keine praktische Bedeutung; es ist so formuliert, um die Theorie der NP-Vollständigkeit auf Cliquenfindungsprobleme anzuwenden .

Das Cliquenproblem und das Unabhängige Mengenproblem sind komplementär: Eine Clique in $G$ ist eine unabhängige Menge im Komplementgraphen von $G$ und umgekehrt. Daher können viele Berechnungsergebnisse gleich gut auf jedes Problem angewendet werden, und einige Forschungsarbeiten unterscheiden nicht klar zwischen den beiden Problemen. Die beiden Probleme haben jedoch unterschiedliche Eigenschaften, wenn sie auf eingeschränkte Familien von Graphen angewendet werden. Zum Beispiel kann das Cliquenproblem für planare Graphen in polynomieller Zeit gelöst werden, während das Problem der unabhängigen Menge auf planaren Graphen NP-hart bleibt.

Algorithmen

Finden einer einzelnen maximalen Clique

Eine maximale Clique, manchmal auch Inklusionsmaximal genannt, ist eine Clique, die nicht in einer größeren Clique enthalten ist. Daher ist jede Clique in einer maximalen Clique enthalten. Maximale Cliquen können sehr klein sein. Ein Graph kann eine nicht-maximale Clique mit vielen Scheitelpunkten und eine separate Clique der Größe 2 enthalten, die maximal ist. Während eine maximale (dh größte) Clique notwendigerweise maximal ist, gilt das Umgekehrte nicht. Es gibt einige Arten von Graphen, in denen jede maximale Clique maximal ist; dies sind die Komplemente der gut abgedeckten Graphen , in denen jede maximale unabhängige Menge maximal ist. Andere Graphen haben jedoch maximale Cliquen, die nicht maximal sind.

Eine einzelne maximale Clique kann durch einen einfachen Greedy-Algorithmus gefunden werden . Beginnen Sie mit einer beliebigen Clique (z. B. einem einzelnen Scheitelpunkt oder sogar der leeren Menge), und vergrößern Sie die aktuelle Clique um einen Scheitelpunkt nach dem anderen, indem Sie die verbleibenden Scheitelpunkte des Graphen durchlaufen. Füge für jeden Knoten $v$ , den diese Schleife untersucht, $v$ zur Clique hinzu, wenn er an jeden Knoten angrenzt, der sich bereits in der Clique befindet, und verwerfe andernfalls $v$ . Dieser Algorithmus läuft in linearer Zeit . Wegen der Leichtigkeit des Auffindens maximaler Cliquen und ihrer potentiell geringen Größe wurde dem viel schwierigeren algorithmischen Problem des Auffindens einer maximalen oder anderweitig großen Clique mehr Aufmerksamkeit geschenkt. Einige Forschungen zu parallelen Algorithmen haben jedoch das Problem untersucht, eine maximale Clique zu finden. Insbesondere hat sich das Problem des Auffindens der lexikographisch ersten maximalen Clique (die durch den obigen Algorithmus gefunden wurde) für die Klasse der polynomialen Zeitfunktionen als vollständig erwiesen . Dieses Ergebnis impliziert, dass es unwahrscheinlich ist, dass das Problem innerhalb der parallelen Komplexitätsklasse NC lösbar ist .

Cliquen fester Größe

Man kann mit einem Brute-Force-Algorithmus testen, ob ein Graph $G$ eine $k-$ Vertex-Clique enthält, und jede solche Clique finden, die er enthält . Dieser Algorithmus untersucht jeden Teilgraphen mit $k$ Ecken und prüft, ob er eine Clique bildet. Es braucht Zeit $O$ $($ $n$ $k$ $k$ $2$ $)$ , wie durch die große O - Notation ausgedrückt . Dies liegt daran, dass es $O$ $($ $n$ $k$ $)$ Untergraphen zu überprüfen gibt, von denen jeder $O$ $($ $k$ $2$ $)$ Kanten hat, deren Vorhandensein in $G$ überprüft werden muss. Somit kann das Problem immer dann in polynomieller Zeit gelöst werden, wenn $k$ eine feste Konstante ist. Wenn $k$ jedoch keinen festen Wert hat, sondern stattdessen als Teil der Eingabe des Problems variieren kann, ist die Zeit exponentiell.

Der einfachste nichttriviale Fall des Cliquenfindungsproblems besteht darin, ein Dreieck in einem Graphen zu finden oder äquivalent zu bestimmen, ob der Graph dreiecksfrei ist . In einem Graphen $G$ mit $m$ Kanten darf es höchstens $Θ(m 3/2)$ Dreiecke geben (mit großer Theta-Notation, um anzuzeigen, dass diese Schranke eng ist). Der schlimmste Fall für diese Formel tritt ein, wenn $G$ selbst eine Clique ist. Daher müssen Algorithmen zum Auflisten aller Dreiecke im schlimmsten Fall (unter Verwendung großer Omega-Notation ) mindestens $Ω(m 3/2)$ Zeit benötigen , und es sind Algorithmen bekannt, die dieser Zeitgrenze entsprechen. Zum Beispiel Chiba & Nishizeki (1985) beschreibt einen Algorithmus, der die Eckpunkte , um vom höchsten Grad zum niedrigsten sortiert und durchläuft dann durch jeden Scheitelpunkt $v$ in der sortierten Liste, für Dreiecken suchen, sind $v$ und enthalten keine vorherigen Vertex in der aufführen. Dazu markiert der Algorithmus alle Nachbarn von $v$ , durchsucht alle Kanten, die auf einen Nachbarn von $v fallen, gibt$ ein Dreieck für jede Kante aus, die zwei markierte Endpunkte hat, entfernt dann die Markierungen und löscht $v$ aus dem Graphen. Wie die Autoren zeigen, ist die Zeit für diesen Algorithmus proportional zur Arborizität des Graphen (bezeichnet als $a (G)$ ) multipliziert mit der Anzahl der Kanten, die $O (m a (G)) ist$ . Da die Arborizität höchstens $O (m 1/2)$ beträgt , läuft dieser Algorithmus in der Zeit $O (m 3/2)$ . Allgemeiner gesagt können alle $k-$ Scheitelcliquen durch einen ähnlichen Algorithmus aufgelistet werden, der Zeit proportional zur Anzahl der Kanten multipliziert mit der Arborizität hoch $(k - 2) benötigt$ . Für Graphen konstanter Arborizität, wie planare Graphen (oder im Allgemeinen Graphen aus einer beliebigen nicht-trivialen Familie von kleinen geschlossenen Graphen ), benötigt dieser Algorithmus $O (m)$ Zeit, was optimal ist, da er in der Größe der Eingabe linear ist.

Wünscht man nur ein einzelnes Dreieck oder die Gewissheit, dass der Graph dreiecksfrei ist, sind schnellere Algorithmen möglich. Wie Itai & Rodeh (1978) beobachten, enthält der Graph genau dann ein Dreieck, wenn seine Adjazenzmatrix und das Quadrat der Adjazenzmatrix Einträge ungleich Null in derselben Zelle enthalten. Daher können schnelle Matrixmultiplikationstechniken angewendet werden, um Dreiecke in der Zeit $O (n 2,376) zu finden$ . Alon, Yuster & Zwick (1994) verwendet Multiplikation schnell Matrix die zur Verbesserung der $O (m 3/2)$ Algorithmus für die Suche nach Dreiecke $O (m 1,41)$ . Diese auf schneller Matrixmultiplikation basierenden Algorithmen wurden auch auf Probleme des Auffindens von $k-$ Cliquen für größere Werte von $k erweitert$ .

Auflistung aller maximalen Cliquen

Nach Moon & Moser (1965) hat jeder $n-$ Knotengraph höchstens $3 n /3$ maximale Cliquen. Sie können mit dem Bron-Kerbosch-Algorithmus aufgelistet werden , einem rekursiven Backtracking- Verfahren von Bron & Kerbosch (1973) . Das rekursive Hauptunterprogramm dieser Prozedur hat drei Argumente: eine teilweise konstruierte (nicht-maximale) Clique, eine Menge von Kandidaten-Scheitelpunkten, die der Clique hinzugefügt werden könnten, und eine weitere Menge von Scheitelpunkten, die nicht hinzugefügt werden sollten (da dies dazu führen würde, an eine bereits gefundene Clique). Der Algorithmus versucht, die Kandidatenscheitelpunkte nacheinander zur partiellen Clique hinzuzufügen, wobei für jeden ein rekursiver Aufruf erfolgt. Nachdem jeder dieser Scheitelpunkte ausprobiert wurde, verschiebt es ihn zu dem Satz von Scheitelpunkten, der nicht erneut hinzugefügt werden soll. Es kann gezeigt werden, dass Varianten dieses Algorithmus die Worst-Case-Laufzeit $O (3 n /3) haben$ , die der Anzahl der Cliquen entspricht, die möglicherweise aufgelistet werden müssen. Daher bietet dies eine im schlimmsten Fall optimale Lösung für das Problem der Auflistung aller maximalen Cliquen. Darüber hinaus wurde allgemein berichtet, dass der Bron-Kerbosch-Algorithmus in der Praxis schneller ist als seine Alternativen.

Wenn die Anzahl der Cliquen jedoch deutlich kleiner ist als der schlimmste Fall, können andere Algorithmen vorzuziehen sein. Wie Tsukiyama et al. (1977) gezeigt, ist es auch möglich, alle maximalen Cliquen in einem Graphen in einer polynomiellen Zeit pro erzeugter Clique aufzulisten. Ein Algorithmus wie der ihre, bei dem die Laufzeit von der Ausgabegröße abhängt, wird als ausgabesensitiver Algorithmus bezeichnet . Ihr Algorithmus basiert auf den folgenden zwei Beobachtungen, die die maximalen Cliquen des gegebenen Graphen $G$ mit den maximalen Cliquen eines Graphen $G \ v in$ Beziehung setzen, der durch Entfernen eines beliebigen Knotens $v$ aus $G gebildet wird$ :

Für jede maximale Clique $K$ von $G \ v$ bildet entweder $K$ weiterhin eine maximale Clique in $G$ oder $K ⋃ {v}$ bildet eine maximale Clique in $G$ . Daher hat $G$ mindestens so viele maximale Cliquen wie $G \ v$ .
Jede maximale Clique in $G$ , die kein $v$ enthält, ist eine maximale Clique in $G \ v$ , und jede maximale Clique in $G$ , die $v$ enthält, kann aus einer maximalen Clique $K$ in $G \ v gebildet$ werden, indem $v$ hinzugefügt und die Nicht-Nachbarn entfernt werden von $v$ aus $K$ .

Unter Verwendung dieser Beobachtungen können sie alle maximalen Cliquen in $G$ durch einen rekursiven Algorithmus erzeugen, der willkürlich eine Ecke $v$ wählt und dann für jede maximale Clique $K$ in $G \ v$ sowohl $K$ als auch die Clique ausgibt, die durch Addieren von $v$ zu $K$ und Entfernen des Nicht- -Nachbarn $v$ . Einige Cliquen von $G$ können jedoch auf diese Weise aus mehr als einer Elternclique von $G \ v erzeugt werden$ , sodass sie Duplikate eliminieren, indem sie eine Clique in $G$ nur dann ausgeben, wenn ihr Elternteil in $G \ v$ unter allen möglichen Elterncliquen lexikographisch maximal ist. Auf der Grundlage dieses Prinzips zeigen sie, dass alle maximalen Cliquen in $G$ in der Zeit $O (mn)$ pro Clique erzeugt werden können, wobei $m$ die Anzahl der Kanten in $G$ und $n$ die Anzahl der Ecken ist. Chiba & Nishizeki (1985) verbessern dies auf $O(ma)$ pro Clique, wobei $a$ die Arborizität des gegebenen Graphen ist. Makino & Uno (2004) bieten einen alternativen ausgabeempfindlichen Algorithmus basierend auf schneller Matrixmultiplikation. Johnson & Yannakakis (1988) zeigen, dass es sogar möglich ist, alle maximalen Cliquen in lexikographischer Reihenfolge mit polynomialer Verzögerung pro Clique aufzulisten. Die Wahl der Ordnung ist jedoch für die Effizienz dieses Algorithmus wichtig: Für die Umkehrung dieser Ordnung gibt es keinen Polynomial-Delay-Algorithmus, es sei denn, P = NP .

Aufgrund dieses Ergebnisses ist es möglich, alle maximalen Cliquen in polynomialer Zeit für Graphenfamilien aufzulisten, in denen die Anzahl der Cliquen polynomiell beschränkt ist. Diese Familien umfassen Sehnengraphen , vollständige Graphen , dreiecksfreie Graphen , Intervallgraphen , Graphen mit beschränkter Boxizität und planare Graphen . Insbesondere weisen die planaren Graphen $O (n)$ Cliquen höchstens konstanter Größe auf, die in linearer Zeit aufgelistet werden können. Dasselbe gilt für jede Familie von Graphen, die sowohl dünn besetzt (mit einer Anzahl von Kanten, die höchstens konstant mal der Anzahl von Ecken ist) als auch geschlossen unter der Operation des Nehmens von Untergraphen ist.

Finden von maximalen Cliquen in beliebigen Graphen

Es ist möglich, die maximale Clique oder die Cliquennummer eines beliebigen n- Knotengraphen in der Zeit $O (3 n /3) = O (1.4422 n) zu finden,$ indem man einen der oben beschriebenen Algorithmen verwendet, um alle maximalen Cliquen in $aufzulisten$ den Graphen und gibt den größten zurück. Für diese Variante des Cliquenproblems sind jedoch bessere Worst-Case-Zeitgrenzen möglich. Der Algorithmus von Tarjan & Trojanowski (1977) löst dieses Problem in der Zeit $O (2 n /3) = O (1,2599 n)$ . Es handelt sich um ein rekursives Backtracking-Schema, das dem des Bron-Kerbosch-Algorithmus ähnlich ist, jedoch einige rekursive Aufrufe eliminieren kann, wenn gezeigt werden kann, dass die innerhalb des Aufrufs gefundenen Cliquen suboptimal sind. Jian (1986) verbesserte die Zeit auf $O (2 0,304 n) = O (1,2346 n)$ und Robson (1986) verbesserte sie auf $O (2 0,276 n) = O (1.2108 n)$ Zeit, auf Kosten einer größeren Raumnutzung . Der Algorithmus von Robson kombiniert ein ähnliches Backtracking-Schema (mit einer komplizierteren Fallanalyse) und eine dynamische Programmiertechnik , bei der die optimale Lösung für alle kleinen zusammenhängenden Teilgraphen des Komplementgraphen vorberechnet wird . Diese Teillösungen werden verwendet, um die Backtracking-Rekursion abzukürzen. Der schnellste heute bekannte Algorithmus ist eine verfeinerte Version dieser Methode von Robson (2001), die in der Zeit $O (2 0,249 n) = O (1.1888 n) läuft$ .

Es gab auch umfangreiche Forschungen zu heuristischen Algorithmen zur Lösung von Maximum-Clique-Problemen ohne Worst-Case-Laufzeitgarantien, basierend auf Methoden wie Branch and Bound , lokale Suche , Greedy-Algorithmen und Constraint-Programmierung . Nicht standardmäßige Computermethoden, die zum Auffinden von Cliquen vorgeschlagen wurden, umfassen DNA-Computing und adiabatische Quantenberechnung . Das Maximum-Clique-Problem war Gegenstand einer von DIMACS in den Jahren 1992–1993 gesponserten Implementierungs-Challenge und einer öffentlich zugänglichen Sammlung von Grafiken, die als Benchmarks für die Challenge verwendet wurden.

Spezielle Klassen von Graphen

In diesem Permutationsgraphen entsprechen die maximalen Cliquen den längsten abnehmenden Teilfolgen (4,3,1) und (4,3,2) der definierenden Permutation.

Planare Graphen und andere Familien von dünn besetzten Graphen wurden oben diskutiert: Sie haben linear viele maximale Cliquen begrenzter Größe, die in linearer Zeit aufgelistet werden können. Insbesondere für planare Graphen kann jede Clique nach dem Satz von Kuratowski höchstens vier Ecken haben .

Perfekte Graphen werden durch die Eigenschaft definiert, dass ihre Cliquenzahl ihrer chromatischen Zahl entspricht und dass diese Gleichheit auch in jedem ihrer induzierten Teilgraphen gilt . Für perfekte Graphen ist es möglich, eine maximale Clique in polynomieller Zeit zu finden, indem ein Algorithmus verwendet wird, der auf semidefiniter Programmierung basiert . Diese Methode ist jedoch komplex und nicht kombinatorisch, und für viele Unterklassen perfekter Graphen wurden spezielle Algorithmen zur Cliquenfindung entwickelt. In dem Komplementgraph von bipartiten Graphen , Kőnig Theorem der maximale Clique Problem mit Hilfe von Techniken für gelöst werden kann Matching . In einer anderen Klasse perfekter Graphen, den Permutationsgraphen , ist eine maximale Clique eine längste abnehmende Teilfolge der Permutation, die den Graphen definiert, und kann unter Verwendung bekannter Algorithmen für das Problem der längsten abnehmenden Teilfolge gefunden werden. Umgekehrt kann jede Instanz des längsten abnehmenden Teilfolgenproblems äquivalent als ein Problem des Findens einer maximalen Clique in einem Permutationsgraphen beschrieben werden. Sogar Pnueli & Lempel (1972) bieten einen alternativen quadratischen Algorithmus für maximale Cliquen in Vergleichbarkeitsgraphen , einer breiteren Klasse perfekter Graphen, die als Sonderfall die Permutationsgraphen einschließen. In Akkord-Diagramme können die maximalen Cliquen durch die Auflistung der Eckpunkte in einer Eliminations Ordnung, und die Überprüfung der Clique finden Nachbarschaften jedes Vertex in dieser Reihenfolge.

In einigen Fällen können diese Algorithmen auch auf andere, nicht perfekte Klassen von Graphen ausgedehnt werden. Zum Beispiel ist in einem Kreisgraphen die Nachbarschaft jedes Scheitelpunkts ein Permutationsgraph, so dass eine maximale Clique in einem Kreisgraphen gefunden werden kann, indem der Permutationsgraphalgorithmus auf jede Nachbarschaft angewendet wird. In ähnlicher Weise gibt es in einem Einheitsscheibengraphen (mit einer bekannten geometrischen Darstellung) einen polynomialen Zeitalgorithmus für maximale Cliquen basierend auf der Anwendung des Algorithmus für Komplemente von zweiteiligen Graphen auf gemeinsame Nachbarschaften von Scheitelpunktpaaren.

Das algorithmische Problem, eine maximale Clique in einem zufälligen Graphen zu finden , der aus dem Erdős-Rényi-Modell stammt (in dem jede Kante mit Wahrscheinlichkeit $1/2$ unabhängig von den anderen Kanten auftritt ) wurde von Karp (1976) vorgeschlagen . Da die maximale Clique in einem Zufallsgraphen mit hoher Wahrscheinlichkeit eine logarithmische Größe hat, kann sie durch eine Brute-Force-Suche in der erwarteten Zeit $2 O (log 2 n) gefunden werden$ . Dies ist eine quasi-polynomiale Zeitschranke . Obwohl die Cliquenzahl solcher Graphen normalerweise sehr nahe bei $2 log 2 n liegt$ , finden einfache Greedy-Algorithmen sowie ausgefeiltere randomisierte Approximationstechniken nur Cliquen mit der Größe $log 2 n$ , die halb so groß ist. Die Anzahl der maximalen Cliquen in solchen Graphen ist mit hoher Wahrscheinlichkeit exponentiell in $log 2 n$ , was verhindert, dass Methoden, die alle maximalen Cliquen auflisten, in polynomieller Zeit laufen. Wegen der Schwierigkeit dieses Problems haben mehrere Autoren das Planted-Clique- Problem untersucht, das Clique-Problem auf zufälligen Graphen, die durch Hinzufügen großer Cliquen erweitert wurden. Während spektraler Methoden und semidefinite Programmierung versteckt Cliquen der Größe erfassen kann $Ω (\sqrt n)$ , keine sind Polynomialzeit-Algorithmen derzeit bekannten diejenigen von Größe zu erkennen $o (\sqrt n)$ (ausgedrückt mit wenig-o - Notation ).

Näherungsalgorithmen

Mehrere Autoren haben Näherungsalgorithmen in Betracht gezogen , die versuchen, eine Clique oder eine unabhängige Menge zu finden, die zwar nicht maximal ist, aber eine Größe hat, die dem Maximum so nahe kommt, wie es in polynomieller Zeit gefunden werden kann. Obwohl sich ein Großteil dieser Arbeit auf unabhängige Mengen in dünn besetzten Graphen konzentrierte, ein Fall, der für das komplementäre Cliquenproblem keinen Sinn ergibt, gab es auch Arbeiten an Approximationsalgorithmen, die solche sparse Annahmen nicht verwenden.

Feige (2004) beschreibt einen polynomialen Zeitalgorithmus, der eine Clique der Größe $Ω((log n /log log n) 2)$ in jedem Graphen findet, der die Cliquennummer $Ω(n /log k n)$ für eine beliebige Konstante $k hat$ . Indem dieser Algorithmus verwendet wird, wenn die Cliquenzahl eines gegebenen Eingabegraphen zwischen $n /log n$ und $n /log 3 n liegt$ , Wechsel zu einem anderen Algorithmus von Boppana & Halldórsson (1992) für Graphen mit höheren Cliquenzahlen und Auswahl einer zwei- Vertex-Clique Wenn beide Algorithmen nichts finden, bietet Feige einen Approximationsalgorithmus an, der eine Clique mit einer Anzahl von Vertices innerhalb eines Faktors von $O(n (log log n) 2 /log 3 n)$ des Maximums findet. Obwohl das Näherungsverhältnis dieses Algorithmus schwach ist, ist er das bisher bekannteste. Die nachfolgend beschriebenen Ergebnisse der Näherungshärte legen nahe, dass es keinen Näherungsalgorithmus mit einem Näherungsverhältnis geben kann, das deutlich kleiner als linear ist.

Untere Schranken

NP-Vollständigkeit

Die 3-CNF-Erfüllbarkeitsinstanz (x x ∨ y) ∧ (~x ∨ ~y ∨ ~y) ∧ (~x ∨ y ∨ y) reduziert auf Clique. Die grünen Eckpunkte bilden eine 3-Clique und entsprechen einer befriedigenden Zuordnung.

Das Cliquenentscheidungsproblem ist NP-vollständig . Es war eines der ursprünglichen 21 Probleme von Richard Karp, die in seinem 1972 erschienenen Aufsatz "Reducibility Among Combinatorial Problems" als NP-vollständig gezeigt wurden. Dieses Problem wurde auch in Stephen Cooks Artikel erwähnt, der die Theorie der NP-vollständigen Probleme vorstellt. Wegen der Härte des Entscheidungsproblems ist auch das Problem, eine maximale Clique zu finden, NP-schwer. Wenn man es lösen könnte, könnte man auch das Entscheidungsproblem lösen, indem man die Größe der maximalen Clique mit dem im Entscheidungsproblem eingegebenen Größenparameter vergleicht.

Der NP-Vollständigkeitsbeweis von Karp ist eine Viele-Eins-Reduktion des Booleschen Erfüllbarkeitsproblems . Es beschreibt, wie Boolesche Formeln in konjunktiver Normalform (CNF) in äquivalente Instanzen des Maximum-Clique-Problems übersetzt werden. Erfüllbarkeit wiederum wurde im Cook-Levin-Theorem als NP-vollständig bewiesen . Aus einer gegebenen CNF-Formel bildet Karp einen Graphen, der für jedes Paar $(v, c)$ einen Scheitelpunkt hat , wobei $v$ eine Variable oder ihre Negation ist und $c$ eine Klausel in der Formel ist, die $v$ enthält . Zwei dieser Knoten sind durch eine Kante verbunden, wenn sie kompatible Variablenzuweisungen für verschiedene Klauseln darstellen. Das heißt, es gibt immer dann eine Kante von $(v, c)$ nach $(u, d),$ wenn $c \neq d$ und $u$ und $v$ keine Negationen des anderen sind. Wenn $k$ die Anzahl der Klauseln in der CNF-Formel bezeichnet, dann repräsentieren die $k-$ Scheitelcliquen in diesem Graphen konsistente Möglichkeiten , einigen ihrer Variablen Wahrheitswerte zuzuweisen , um die Formel zu erfüllen. Daher ist die Formel genau dann erfüllbar, wenn eine $k$ -Scheitelclique existiert.

Einige NP-vollständige Probleme (wie das Travelling-Salesman-Problem in planaren Graphen ) können in einer Zeit gelöst werden, die in einer sublinearen Funktion des Eingabegrößenparameters $n$ exponentiell ist , signifikant schneller als eine Brute-Force-Suche. Es ist jedoch unwahrscheinlich, dass eine solche subexponentielle Zeitschranke für das Cliquenproblem in beliebigen Graphen möglich ist, da dies ähnliche subexponentielle Schranken für viele andere NP-vollständige Standardprobleme implizieren würde.

Schaltungskomplexität

Eine monotone Schaltung zum Erfassen einer

k-

Clique in einem

n-

Scheitelgraphen für

k = 3

und

n = 4

. Jeder Eingang in die Schaltung codiert das Vorhandensein oder Fehlen einer bestimmten (roten) Kante im Graphen. Die Schaltung verwendet ein internes Und-Gatter, um jede potentielle

k-

Clique zu erkennen .

Die Rechenschwierigkeiten des Cliquenproblems haben dazu geführt, dass es verwendet wird, um mehrere untere Schranken der Schaltungskomplexität zu beweisen . Die Existenz einer Clique einer bestimmten Größe ist eine monotone Grapheigenschaft , was bedeutet, dass wenn eine Clique in einem gegebenen Graphen existiert, sie in jedem Supergraphen existiert . Da diese Eigenschaft monoton ist, muss eine monotone Schaltung existieren, die nur und Gatter und oder Gatter verwendet , um das Cliquenentscheidungsproblem für eine gegebene feste Cliquengröße zu lösen. Die Größe dieser Kreise kann jedoch als eine superpolynomielle Funktion der Anzahl der Knoten und der Cliquengröße nachgewiesen werden, die in der Kubikwurzel der Anzahl der Knoten exponentiell ist. Selbst wenn eine kleine Anzahl von NOT-Gattern erlaubt ist, bleibt die Komplexität superpolynomiell. Außerdem muss die Tiefe einer monotonen Schaltung für das Cliquenproblem unter Verwendung von Gattern mit beschränktem Auffächern mindestens ein Polynom in der Cliquengröße sein.

Komplexität des Entscheidungsbaums

Ein einfacher Entscheidungsbaum, um das Vorhandensein einer 3-Clique in einem 4-Scheitel-Graphen zu erkennen. Es verwendet bis zu 6 Fragen der Form "Existiert die rote Kante?", die der optimalen Schranke n ( n − 1)/2 entsprechen.

Die (deterministische) Entscheidungsbaumkomplexität zur Bestimmung einer Grapheigenschaft ist die Anzahl von Fragen der Form "Gibt es eine Kante zwischen Knoten $u$ und Knoten $v$ ?" die im schlimmsten Fall beantwortet werden müssen, um festzustellen, ob ein Graph eine bestimmte Eigenschaft besitzt. Das heißt, es ist die minimale Höhe eines booleschen Entscheidungsbaums für das Problem. Es sind $n (n - 1)/2$ mögliche Fragen zu stellen. Daher kann jede Grapheigenschaft mit höchstens $n (n - 1)/2$ Fragen bestimmt werden. Es ist auch möglich, die zufällige und Quantenentscheidungsbaumkomplexität einer Eigenschaft zu definieren, die erwartete Anzahl von Fragen (für eine Eingabe im ungünstigsten Fall), die ein randomisierter oder Quantenalgorithmus beantwortet haben muss, um korrekt zu bestimmen, ob der gegebene Graph die Eigenschaft hat .

Da die Eigenschaft, eine Clique zu enthalten, monoton ist, wird sie durch die Aanderaa-Karp-Rosenberg-Vermutung abgedeckt , die besagt, dass die deterministische Entscheidungsbaumkomplexität zur Bestimmung einer nicht-trivialen monotonen Grapheigenschaft genau $n (n - 1)/2 ist$ . Für beliebige monotone Grapheigenschaften bleibt diese Vermutung unbewiesen. Für deterministische Entscheidungsbäume und für jedes $k$ im Bereich $2 \leq k \leq n$ wurde jedoch von Bollobás (1976) gezeigt, dass die Eigenschaft, eine $k-$ Clique zu enthalten, eine Entscheidungsbaumkomplexität von genau $n (n - 1)/2 hat$ . Deterministische Entscheidungsbäume erfordern auch eine exponentielle Größe, um Cliquen zu erkennen, oder eine große polynomielle Größe, um Cliquen begrenzter Größe zu erkennen.

Die Aanderaa-Karp-Rosenberg-Vermutung besagt auch, dass die randomisierte Entscheidungsbaumkomplexität nichttrivialer monotoner Funktionen $Θ(n 2) ist$ . Die Vermutung bleibt wiederum unbewiesen, wurde aber für die Eigenschaft aufgelöst, eine $k-$ Clique für $2 k \leq n zu enthalten$ . Diese Eigenschaft ist bekannt , randomisierten Entscheidungsbaum Komplexität haben $Θ (n 2)$ . Für Quantenentscheidungsbäume ist die bekannteste untere Schranke $Ω(n)$ , aber für den Fall $k 3$ ist kein Matching-Algorithmus bekannt .

Widerspenstigkeit mit festen Parametern

Parametrisierte Komplexität ist die komplexitätstheoretische Untersuchung von Problemen, die von Natur aus mit einem kleinen ganzzahligen Parameter $k ausgestattet sind$ und bei denen das Problem mit zunehmendem $k$ schwieriger wird, wie z. B. das Auffinden von $k$ -Cliquen in Graphen. Ein Problem wird als behandelbar mit festen Parametern bezeichnet, wenn es einen Algorithmus zu dessen Lösung auf Eingaben der Größe $n$ und eine Funktion $f gibt$ , so dass der Algorithmus in der Zeit $f (k) n O (1)$ läuft . Das heißt, es ist mit festen Parametern lenkbar, wenn es in polynomieller Zeit für jeden festen Wert von $k$ gelöst werden kann und darüber hinaus, wenn der Exponent des Polynoms nicht von $k$ abhängt .

Um $k-$ Scheitelcliquen zu finden, hat der Brute-Force-Suchalgorithmus eine Laufzeit $O(n k k 2)$ . Da der Exponent von $n$ von $k$ abhängt , ist dieser Algorithmus nicht mit festen Parametern bearbeitbar. Obwohl sie durch schnelle Matrixmultiplikation verbessert werden kann, hat die Laufzeit immer noch einen Exponenten, der in $k$ linear ist. Obwohl die Laufzeit bekannter Algorithmen für das Cliquenproblem also für jedes feste $k$ polynomiell ist , reichen diese Algorithmen nicht für feste Parameter Lenkbarkeit. Downey & Fellows (1995) definierten eine Hierarchie parametrisierter Probleme, die W-Hierarchie, von der sie vermuteten, dass sie keine lenkbaren Algorithmen mit festen Parametern hatte. Sie haben bewiesen, dass unabhängige Menge (oder gleichwertig Clique) für die erste Ebene dieser Hierarchie W[1] schwierig ist . Somit hat Clique nach ihrer Vermutung keinen lenkbaren Algorithmus mit festen Parametern. Darüber hinaus liefert dieses Ergebnis die Grundlage für Beweise der W[1]-Härte vieler anderer Probleme und dient somit als Analogon zum Cook-Levin-Theorem für parametrisierte Komplexität.

Chenet al. (2006) zeigten, dass das Auffinden von $k-$ Scheitelcliquen nicht in der Zeit $n o (k) erfolgen kann, es$ sei denn, die exponentielle Zeithypothese versagt. Dies liefert wiederum den Beweis, dass kein lenkbarer Algorithmus mit festen Parametern möglich ist.

Obwohl es unwahrscheinlich ist, dass die Probleme des Auflistens maximaler Cliquen oder des Findens maximaler Cliquen mit dem Parameter $k$ mit festen Parametern handhabbar sind, können sie für andere Parameter der Instanzkomplexität mit festen Parametern handhabbar sein. Zum Beispiel ist bekannt, dass beide Probleme mit festen Parametern behandelbar sind, wenn sie durch die Entartung des Eingabegraphen parametrisiert werden .

Härte der Näherung

Ein Diagramm der Kompatibilitätsbeziehungen zwischen 2-Bit-Abtastwerten von 3-Bit-Beweiszeichenfolgen. Jede maximale Clique (Dreieck) in diesem Graphen repräsentiert alle Möglichkeiten, einen einzelnen 3-Bit-String abzutasten. Der Beweis der Unannäherung des Cliquenproblems beinhaltet induzierte Teilgraphen von analog definierten Graphen für größere Bitzahlen .

Schwache Ergebnisse, die darauf hindeuten, dass sich das Cliquenproblem nur schwer annähern könnte, sind seit langem bekannt. Garey & Johnson (1978) beobachteten, dass die Cliquenzahl, da sie kleine ganzzahlige Werte annimmt und NP-schwer zu berechnen ist, kein vollständig polynomiales Approximationsschema haben kann . Wenn eine zu genaue Näherung verfügbar wäre, würde das Runden des Wertes auf eine ganze Zahl die genaue Cliquenzahl ergeben. Bis Anfang der 1990er Jahre war jedoch wenig mehr bekannt, als mehrere Autoren begannen, Verbindungen zwischen der Approximation maximaler Cliquen und probabilistisch überprüfbaren Beweisen herzustellen . Sie verwendeten diese Verbindungen, um die Härte der Näherungsergebnisse für das Maximum-Clique-Problem zu beweisen . Nach vielen Verbesserungen dieser Ergebnisse ist nun bekannt, dass es für jede reelle Zahl $ε > 0$ keinen Polynomialzeitalgorithmus geben kann, der die maximale Clique auf einen Faktor besser als $O (n 1 - ε)$ approximiert , es sei denn, P = NP .

Die grobe Idee dieser Unnäherungsergebnisse besteht darin, einen Graphen zu bilden, der ein probabilistisch überprüfbares Beweissystem für ein NP-vollständiges Problem wie das Boolesche Erfüllbarkeitsproblem darstellt. In einem probabilistisch überprüfbaren Beweissystem wird ein Beweis als eine Folge von Bits dargestellt. Eine Instanz des Erfüllbarkeitsproblems sollte genau dann einen gültigen Beweis haben, wenn sie erfüllbar ist. Der Beweis wird durch einen Algorithmus geprüft, der nach einer Polynomialzeitberechnung der Eingabe des Erfüllbarkeitsproblems eine kleine Anzahl zufällig ausgewählter Positionen der Beweiskette untersucht. Abhängig davon, welche Werte in dieser Bitprobe gefunden werden, akzeptiert der Prüfer den Beweis entweder oder lehnt ihn ab, ohne den Rest der Bits zu betrachten. Falsche Negative sind nicht erlaubt: Ein gültiger Nachweis muss immer akzeptiert werden. Ein ungültiger Nachweis kann jedoch manchmal fälschlicherweise akzeptiert werden. Für jeden ungültigen Beweis muss die Wahrscheinlichkeit, dass der Prüfer ihn akzeptiert, gering sein.

Um ein solches probabilistisch überprüfbares Beweissystem in ein Cliquenproblem zu überführen, bildet man für jeden möglichen akzeptierenden Durchlauf des Beweisprüfers einen Graphen mit einer Ecke. Das heißt, ein Scheitelpunkt wird durch eine der möglichen zufälligen Auswahlen von zu untersuchenden Positionssätzen und durch Bitwerte für jene Positionen definiert, die den Prüfer veranlassen würden, den Beweis zu akzeptieren. Es kann durch ein Teilwort mit einer 0 oder 1 an jeder untersuchten Stelle und einem Platzhalterzeichen an jeder verbleibenden Stelle dargestellt werden. Zwei Scheitelpunkte sind in diesem Diagramm benachbart, wenn die entsprechenden zwei akzeptierenden Läufe die gleichen Bitwerte an jeder Position sehen, die sie beide untersuchen. Jeder (gültige oder ungültige) Beweisstring entspricht einer Clique, der Menge der akzeptierenden Läufe, die diesen Beweisstring sehen, und alle maximalen Cliquen entstehen auf diese Weise. Eine dieser Cliquen ist genau dann groß, wenn sie einer Beweiszeichenfolge entspricht, die viele Beweisprüfer akzeptieren. Wenn die ursprüngliche Erfüllbarkeitsinstanz erfüllbar ist, hat sie einen gültigen Beweisstring, der von allen Prüfläufen akzeptiert wird, und dieser String entspricht einer großen Clique im Graphen. Wenn die ursprüngliche Instanz jedoch nicht erfüllbar ist, sind alle Prüfzeichenfolgen ungültig, jede Prüfzeichenfolge hat nur eine kleine Anzahl von Prüfläufen, die sie fälschlicherweise akzeptieren, und alle Cliquen sind klein. Wenn man also in polynomieller Zeit zwischen Graphen mit großen Cliquen und Graphen, in denen alle Cliquen klein sind, unterscheiden könnte oder wenn man das Cliquenproblem genau annähern könnte, dann würde die Anwendung dieser Näherung auf die aus Erfüllbarkeitsinstanzen erzeugten Graphen es erfüllbaren Instanzen ermöglichen, von unerfüllbaren Instanzen unterschieden werden. Dies ist jedoch nur möglich, wenn P = NP ist.

Anmerkungen

Verweise

Umfragen und Lehrbücher

Arora, Sanjeev ; Barak, Boaz (2009), Computational Complexity: A Modern Approach , Cambridge University Press, ISBN 978-0-521-42426-4.
Blair, Jean RS; Peyton, Barry (1993), "Eine Einführung in chordal graphs and clique tree", Graphentheorie und dünnbesetzte Matrixberechnung , IMA Vol. Mathematik. Appl., 56 , Springer, New York, S. 1–29, doi : 10.1007/978-1-4613-8369-7_1 , MR 1320296.
Bomze, IM; Budinich, M.; Pardalos, PM; Pelillo, M. (1999), "The maximum clique problem", Handbook of Combinatorial Optimization , 4 , Kluwer Academic Publishers, S. 1–74, CiteSeerX 10.1.1.48.4074.
Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), "34.5.1 The clique problem", Introduction to Algorithms (2. Aufl.), MIT Press und McGraw-Hill, S. 1003–1006, ISBN 0-262-03293-7.
Downey, RG; Fellows, MR (1999), Parametrisierte Komplexität , Springer-Verlag , ISBN 0-387-94883-X.
Golumbic, MC (1980), Algorithmic Graph Theory and Perfect Graphs , Informatik und Angewandte Mathematik, Academic Press , ISBN 0-444-51530-5.
Grötschel, M. ; Lovász, L. ; Schrijver, A. (1988), „9.4 Coloring Perfect Graphs“, Geometrische Algorithmen und kombinatorische Optimierung , Algorithmen und Kombinatorik, 2 , Springer-Verlag , S. 296–298, ISBN 0-387-13624-X.
Gutin, G. (2004), "5.3 Unabhängige Sets und Cliquen", in Gross, JL; Yellen, J. (Hrsg.), Handbook of Graph Theory , Discrete Mathematics & Its Applications, CRC Press, S. 389–402, ISBN 978-1-58488-090-5.
Mügge, Ingo; Rarey, Matthias (2001), "Small molecule docking and score", Reviews in Computational Chemistry , 17 : 1–60, doi : 10.1002/0471224413.ch1 , ISBN 9780471398455.
National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995), Mathematical Challenges from Theoretical/Computational Chemistry , National Academies Press, doi : 10.17226/4886 , ISBN 978-0-309-05097-5.
Pelillo, Marcello (2009), "Heuristiken für maximale Clique und unabhängige Menge", Encyclopedia of Optimization , Springer, S. 1508–1520, doi : 10.1007/978-0-387-74759-0_264.
Plummer, Michael D. (1993), "Well-covered graphs: a survey" , Quaestiones Mathematicae , 16 (3): 253–287, doi : 10.1080/16073606.1993.9631737 , MR 1254158.
Sipser, M. (1996), Einführung in die Rechentheorie , International Thompson Publishing , ISBN 0-534-94728-X.
Skiena, Steven S. (2009), The Algorithm Design Manual (2. Aufl.), Springer, ISBN 978-1-84800-070-4.
Valiente, Gabriel (2002), "Chapter 6: Clique, Independent Set, and Vertex Cover", Algorithms on Trees and Graphs , Springer, S. 299–350, doi : 10.1007/978-3-662-04921-1_6.
Wassermann, Stanley ; Faust, Katherine (1994), Social Network Analysis: Methods and Applications , Structural Analysis in the Social Sciences, 8 , Cambridge University Press, p. 276, ISBN 978-0-521-38707-1.

Bekannte Presse

Kolata, Gina (26. Juni 1990), "In einer Raserei tritt die Mathematik in das Zeitalter der elektronischen Post ein" , The New York Times.

Forschungsartikel

Abello, J.; Pardalos, PM; Resende, MGC (1999), "Über maximale Cliquenprobleme in sehr großen Graphen" (PDF) , in Abello, J.; Vitter, J. (Hrsg.), External Memory Algorithms , DIMACS Series on Discrete Mathematics and Theoretical Computer Science, 50 , American Mathematical Society , S. 119–130, ISBN 0-8218-1184-3.
Alon, N. ; Boppana, R. (1987), "Die monotone Schaltungskomplexität boolescher Funktionen", Combinatorica , 7 (1): 1–22, doi : 10.1007/BF02579196 , S2CID 17397273.
Alon, N. ; Krivelevich, M.; Sudakov, B. (1998), "Finding a large hidden clique in a random graph", Random Structures & Algorithms , 13 (3–4): 457–466, doi : 10.1002/(SICI)1098-2418(199810/12 .) )13:3/4<457::AID-RSA14>3.0.CO;2-W.
Alon, N. ; Yuster, R.; Zwick, U. (1994), "Finden und Zählen von gegebenen Längenzyklen", Proceedings of the 2nd European Symposium on Algorithms, Utrecht, Niederlande , S. 354–364.
Amano, Kazuyuki; Maruoka, Akira (2005), "Eine superpolynomiale untere Schranke für eine Schaltung, die die Cliquenfunktion mit höchstens $(1/6)log log N$ Negation Gates berechnet ", SIAM Journal on Computing , 35 (1): 201–216, doi : 10.1137/S0097539701396959 , HERR 2178806.
Arora, Sanjeev ; Lund, Carsten ; Motwani, Rajeev ; Sudan, Madhu ; Szegedy, Mario (1998), "Beweisprüfung und die Härte von Approximationsproblemen", Journal of the ACM , 45 (3): 501–555, doi : 10.1145/278298.278306 , S2CID 8561542 , ECCC TR98-008. Ursprünglich präsentiert auf dem Symposium on Foundations of Computer Science 1992 , doi : 10.1109/SFCS.1992.267823 .
Arora, S. ; Safra, S. (1998), "Probabilistic testing of proofs: A new characterization of NP", Journal of the ACM , 45 (1): 70–122, doi : 10.1145/273865.273901 , S2CID 751563. Ursprünglich präsentiert auf dem Symposium on Foundations of Computer Science 1992 , doi : 10.1109/SFCS.1992.267824 .
Balas, E.; Yu, CS (1986), "Finding a maximum clique in anarbitrary graph", SIAM Journal on Computing , 15 (4): 1054–1068, doi : 10.1137/0215075.
Barrow, H.; Burstall, R. (1976), "Subgraph Isomorphism, Matching relational Structures and Maximum Cliques", Information Processing Letters , 4 (4): 83–84, doi : 10.1016/0020-0190(76)90049-1.
Battiti, R.; Protasi, M. (2001), "Reactive local search for the maximum clique problem", Algorithmica , 29 (4): 610–637, doi : 10.1007/s004530010074 , S2CID 1800512.
Bollobás, Béla (1976), "Complete subgraphs are elusive", Journal of Combinatorial Theory , Series B, 21 (1): 1–7, doi : 10.1016/0095-8956(76)90021-6 , ISSN 0095-8956.
Boppana, R.; Halldórsson, MM (1992), "Approximating maximum Independent Sets by Ausschluss von Untergraphen", BIT Numerical Mathematics , 32 (2): 180-196, doi : 10.1007/BF01994876 , S2CID 123335474.
Bron, C.; Kerbosch, J. (1973), "Algorithm 457: Finding all cliques of an undirected graph", Communications of the ACM , 16 (9): 575–577, doi : 10.1145/362342.362367 , S2CID 13886709.
Carraghan, R.; Pardalos, PM (1990), "Ein genauer Algorithmus für das maximale Cliquenproblem", Operations Research Letters , 9 (6): 375–382, doi : 10.1016/0167-6377(90)90057-C.
Cazals, F.; Karande, C. (2008), „A note on the problem of reporting maximum cliques“, Theoretical Computer Science , 407 (1): 564–568, doi : 10.1016/j.tcs.2008.05.010.
Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), "Strong Computational Lower Bounds via parametrized Complexity", Journal of Computer and System Sciences , 72 (8): 1346–1367, doi : 10.1016/j.jcss.2006.04.007
Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing , 14 (1): 210–223, doi : 10.1137/0214017.
Kinder, AM; Farhi, E.; Goldstone, J. ; Gutmann, S. (2002), "Finding cliques byquantum adiabatic evolution", Quantum Information and Computation , 2 (3): 181–191, arXiv : quant-ph/0012104 , Bibcode : 2000quant.ph.12104C , doi : 10.26421 /QIC2.3 , S2CID 33643794.
Kinder, AM; Eisenberg, JM (2005), "Quantum algorithms for subset finding", Quantum Information and Computation , 5 (7): 593–604, arXiv : quant-ph/0311038 , Bibcode : 2003quant.ph.11038C , doi : 10.26421/QIC5 0,7 , S2CID 37556989.
Clark, Brent N.; Colbourn, Charles J .; Johnson, David S. (1990), "Unit disk graphs", Discrete Mathematics , 86 (1–3): 165–177, doi : 10.1016/0012-365X(90)90358-O
Cook, SA (1971), "Die Komplexität von Verfahren zum Beweisen von Theoremen" , Proc. 3. ACM Symposium on Theory of Computing , S. 151–158, doi : 10.1145/800157.805047 , S2CID 7573663.
Cook, Stephen A. (1985), "Eine Taxonomie von Problemen mit schnellen parallelen Algorithmen", Information and Control , 64 (1–3): 2–22, doi : 10.1016/S0019-9958(85)80041-3 , MR 0837088.
Tag, William HE; Sankoff, David (1986), "Computational Complexity of Inferring Phylogenies by Kompatibilität", Systematic Zoology , 35 (2): 224–229, doi : 10.2307/2413432 , JSTOR 2413432.
Downey, RG; Fellows, MR (1995), "Fixed-parameter tractability and completeness. II. On completeness for W[1]", Theoretical Computer Science , 141 (1–2): 109–131, doi : 10.1016/0304-3975(94 .) )00097-3.
Eisenbrand, F.; Grandoni, F. (2004), "Über die Komplexität der Clique mit festen Parametern und dominierender Menge", Theoretische Informatik , 326 (1–3): 57–67, doi : 10.1016/j.tcs.2004.05.009.
Eppstein, David ; Löffler, Maarten; Strash, Darren (2013), "Listing all maximum cliques in large sparse real world graphs in near-optimal time", Journal of Experimental Algorithmics , 18 (3): 3.1, arXiv : 1103.0318 , doi : 10.1145/2543629 , S2CID 47515491.
Erdäs, Paul ; Szekeres, George (1935), „Ein kombinatorisches Problem in der Geometrie“ (PDF) , Compositio Mathematica , 2 : 463–470.
Sogar, S. ; Pnueli, A. ; Lempel, A. (1972), "Permutation graphs and transitive graphs", Journal of the ACM , 19 (3): 400–410, doi : 10.1145/321707.321710 , S2CID 9501737.
Fahle, T. (2002), "Simple and fast: Improving a branch-and-bound algorithm for maximum clique", Proc. 10th European Symposium on Algorithms , Lecture Notes in Computer Science, 2461 , Springer-Verlag, S. 47–86, doi : 10.1007/3-540-45749-6_44 , ISBN 978-3-540-44180-9.
Feige, U. (2004), "Approximating maximum clique by remove subgraphs", SIAM Journal on Discrete Mathematics , 18 (2): 219–225, doi : 10.1137/S089548010240415X.
Feige, U. ; Goldwasser, S. ; Lovász, L. ; Safra, S ; Szegedy, M. (1991), "Annähernde Clique ist fast NP-vollständig", Proc. 32. IEEE Symp. on Foundations of Computer Science , S. 2–12, doi : 10.1109/SFCS.1991.185341 , ISBN 0-8186-2445-0, S2CID 46605913.
Feige, U. ; Krauthgamer, R. (2000), "Finding and certifying a large hidden clique in a semirandom graph", Random Structures and Algorithms , 16 (2): 195–208, doi : 10.1002/(SICI)1098-2418(200003)16 :2<195::AID-RSA5>3.0.CO;2-A.
Frank, Ove; Strauss, David (1986), "Markov graphs", Journal of the American Statistical Association , 81 (395): 832–842, doi : 10.2307/2289017 , JSTOR 2289017 , MR 0860518.
Garey, Herr ; Johnson, DS (1978), " " Strong "NP-Vollständigkeit Ergebnisse: Motivation, Beispiele und Implikationen", Journal of the ACM , 25 (3): 499-508, doi : 10,1145 / 322.077,322090 , S2CID 18371269.
Garey, Herr ; Johnson, DS ; Stockmeyer, L. (1976), "Einige vereinfachte NP-vollständige Graphprobleme ", Theoretical Computer Science , 1 (3): 237–267, doi : 10.1016/0304-3975(76)90059-1 , MR 0411240.
Gavril, F. (1973), "Algorithms for a maximum clique and a maximum Independent set of a circle graph", Networks , 3 (3): 261–273, doi : 10.1002/net.3230030305.
Goldmann, M.; Håstad, J. (1992), "A simple Lower Bound for monotone clique using a communication game" (PDF) , Information Processing Letters , 41 (4): 221–226, CiteSeerX 10.1.1.185.3065 , doi : 10.1016/0020 -0190(92)90184-W.
Gröger, Hans Dietmar (1992), "On the randomized complex of monotone graph properties" (PDF) , Acta Cybernetica , 10 (3): 119–127 , abgerufen 2009-10-02
Grosso, A.; Locatelli, M.; Della Croce, F. (2004), „Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem“, Journal of Heuristics , 10 (2): 135–152, doi : 10.1023/B:HEUR.0000026264.51747. 7f , S2CID 40764225.
Halldórsson, MM (2000), "Approximations of Weighted Independent Set and Hereditary Subset Problems", Journal of Graph Algorithms and Applications , 4 (1): 1–16, doi : 10.7155/jgaa.00020.
Hamzaoglu, I.; Patel, JH (1998), "Testsatzverdichtungsalgorithmen für kombinatorische Schaltungen", Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design , S. 283–289, doi : 10.1145/288548.288615 , S2CID 12258606.
Harary, F. ; Ross, IC (1957), "A procedure for clique detection using the group matrix", Sociometry , American Sociological Association, 20 (3): 205–215, doi : 10.2307/2785673 , JSTOR 2785673 , MR 0110590.
Håstad, J. (1999), „Clique is hard to approx within $n 1 - ε$ “, Acta Mathematica , 182 (1): 105–142, doi : 10.1007/BF02392825.
Impagliazzo, R. ; Paturi, R.; Zane, F. (2001), "Welche Probleme haben stark exponentielle Komplexität?", Journal of Computer and System Sciences , 63 (4): 512–530, doi : 10.1006/jcss.2001.1774.
Itai, A.; Rodeh, M. (1978), "Finding a minimum circuit in a graph", SIAM Journal on Computing , 7 (4): 413–423, doi : 10.1137/0207033.
Jerrum, M. (1992), "Large cliques elude the Metropolis process", Random Structures and Algorithms , 3 (4): 347–359, doi : 10.1002/rsa.3240030402.
Jian, T (1986), "An $O (2 0.304 n)$ algorithm forsolving maximum Independent Set problem", IEEE Transactions on Computers , IEEE Computer Society, 35 (9): 847–851, doi : 10.1109/TC.1986.1676847 , ISSN 0018-9340.
Johnson, DS ; Trick, MA , Hrsg. (1996), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 11.–13. Oktober 1993 , DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 26 , American Mathematical Society , ISBN 0-8218-6609-5.
Johnson, DS ; Yannakakis, M. (1988), "On Generating all Maximum Independent Sets", Information Processing Letters , 27 (3): 119–123, doi : 10.1016/0020-0190(88)90065-8.
Karp, Richard M. (1972), "Reduzierbarkeit unter kombinatorischen Problemen", in Miller, RE; Thatcher, JW (Hrsg.), Complexity of Computer Computations (PDF) , New York: Plenum , S. 85–103, archiviert vom Original (PDF) am 29.06.2011 , abgerufen am 17.12.2009.
Karp, Richard M. (1976), „Probabilistic analysis of some combinatorial search problem“, in Traub, JF (Hrsg.), Algorithms and Complexity: New Directions and Recent Results , New York: Academic Press , S. 1–19.
Katayama, K.; Hamamoto, A.; Narihisa, H. (2005), "Eine effektive lokale Suche nach dem maximalen Cliquenproblem", Information Processing Letters , 95 (5): 503–511, doi : 10.1016/j.ipl.2005.05.010.
Khot, S. (2001), "Verbesserte Unnäherungsergebnisse für MaxClique, chromatische Zahl und ungefähre Graphenfärbung", Proc. 42. IEEE Symp. Grundlagen der Informatik , S. 600–609, doi : 10.1109/SFCS.2001.959936 , ISBN 0-7695-1116-3, S2CID 11987483.
Kloks, T.; Kratsch, D.; Müller, H. (2000), "Kleine induzierte Teilgraphen effizient finden und zählen", Information Processing Letters , 74 (3–4): 115–121, doi : 10.1016/S0020-0190(00)00047-8.
Konc, J.; Janežič, D. (2007), "Ein verbesserter Branch-and-Bound-Algorithmus für das Maximum-Clique-Problem" (PDF) , MATCH Communications in Mathematical and in Computer Chemistry , 58 (3): 569–590. Quellcode
Kuhl, FS; Crippen, GM; Friesen, DK (1983), "Ein kombinatorischer Algorithmus zur Berechnung der Ligandenbindung", Journal of Computational Chemistry , 5 (1): 24–34, doi : 10.1002/jcc.540050105 , S2CID 122923018.
Lagarias, Jeffrey C .; Shor, Peter W. (1992), "Keller's cube-tiling conjecture is false in high dimensions", Bulletin of the American Mathematical Society , New Series, 27 (2): 279–283, arXiv : math/9210222 , doi : 10.1090 /S0273-0979-1992-00318-X , MR 1155280 , S2CID 6390600.
Lipton, RJ ; Tarjan, RE (1980), "Applications of a planar separator theorem", SIAM Journal on Computing , 9 (3): 615–627, doi : 10.1137/0209046 , S2CID 12961628.
Liu, Yu; Lu, Jiaheng; Yang, Hua; Xiao, Xiaokui; Wei, Zhewei (2015), "Towards maximum Independent Sets on massive graphs", Proceedings of the 41st International Conference on Very Large Data Bases (VLDB 2015) , Proceedings of the VLDB Endowment, 8 , S. 2122–2133, doi : 10.14778 /2831360.2831366 , hdl : 10138/157292.
Luce, R. Duncan ; Perry, Albert D. (1949), "A method of matrix analysis of group structure", Psychometrika , 14 (2): 95–116, doi : 10.1007/BF02289146 , hdl : 10.1007/BF02289146 , PMID 18152948 , S2CID 16186758.
Mackey, John (2002), "A cube tiling of dimension acht ohne Facesharing", Discrete and Computational Geometry , 28 (2): 275–279, doi : 10.1007/s00454-002-2801-9 , MR 1920144.
Magniez, Frederic; Santha, Miklos; Szegedy, Mario (2007), "Quantum algorithms for the triangle problem", SIAM Journal on Computing , 37 (2): 413–424, arXiv : quant-ph/0310134 , doi : 10.1137/050643684 , S2CID 594494.
Makino, K.; Uno, T. (2004), "New algorithms for enumerating all maximal cliques", Algorithm Theory: SWAT 2004 (PDF) , Lecture Notes in Computer Science, 3111 , Springer-Verlag , S. 260–272, CiteSeerX 10.1.1.138. 705 , doi : 10.1007/978-3-540-27810-8_23.
Meka, Raghu; Potechin, Aaron; Wigderson, Avi (2015), "Sum-of-squares Lower Bounds for Planted Clique", Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC '15) , New York, NY, USA: ACM, pp 87–96, arXiv : 1503.06447 , doi : 10.1145/2746539.2746600 , ISBN 978-1-4503-3536-2, S2CID 2754095.
Mond, Zeuge Jehovas; Moser, L. (1965), "On cliques in graphs", Israel Journal of Mathematics , 3 : 23–28, doi : 10.1007/BF02760024 , MR 0182577 , S2CID 9855414.
Nešetřil, J. ; Poljak, S. (1985), „Über die Komplexität des Untergraphenproblems“, Commentationes Mathematicae Universitatis Carolinae , 26 (2): 415–419.
Östergård, PRJ (2002), "A fast algorithm for the maximum clique problem", Discrete Applied Mathematics , 120 (1–3): 197–207, doi : 10.1016/S0166-218X(01)00290-6.
Ouyang, Q.; Kaplan, PD; Liu, S.; Libchaber, A. (1997), "DNA-Lösung des maximalen Cliquenproblems", Science , 278 (5337): 446–449, Bibcode : 1997Sci...278..446O , doi : 10.1126/science.278.5337.446 , PMID 9334300.
Papadimitriou, Christos H .; Yannakakis, Mihalis (1981), "The clique problem for planar graphs", Information Processing Letters , 13 (4–5): 131–133, doi : 10.1016/0020-0190(81)90041-7 , MR 0651460.
Pardalos, PM; Rogers, GP (1992), "A branch andbound algorithm for the maximum clique problem", Computers & Operations Research , 19 (5): 363–375, doi : 10.1016/0305-0548(92)90067-F.
Razborov, AA (1985), "Untere Grenzen für die monotone Komplexität einiger Boolescher Funktionen", Proceedings of the UdSSR Academy of Sciences (in Russisch), 281 : 798–801. Englische Übersetzung in Sov. Mathematik. Dokl. 31 (1985): 354–357CS1-Wartung: Postscript ( Link ).
Regin, J.-C. (2003), "Verwendung von Constraint-Programmierung zur Lösung des Maximum-Clique-Problems", Proc. 9. Int. Konf. Principles and Practice of Constraint Programming – CP 2003 , Lecture Notes in Computer Science, 2833 , Springer-Verlag , S. 634–648, doi : 10.1007/978-3-540-45193-8_43.
Rhodos, Nikolaus; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), "CLIP: Ähnlichkeitssuche von 3D-Datenbanken mit Cliquenerkennung", Journal of Chemical Information and Computer Sciences , 43 (2): 443–448, doi : 10.1021/ci025605o , PMID 12653507.
Robson, JM (1986), "Algorithmen für maximale unabhängige Sätze", Journal of Algorithms , 7 (3): 425–440, doi : 10.1016/0196-6774(86)90032-5.
Robson, JM (2001), Finden einer maximalen unabhängigen Menge in der Zeit $O (2 n /4)$ .
Rosgen, B; Stewart, L (2007), "Komplexitätsergebnisse auf Graphen mit wenigen Cliquen" , Discrete Mathematics and Theoretical Computer Science , 9 (1): 127–136.
Samudrala, Ram; Moult, John (1998), "Ein graphentheoretischer Algorithmus zur vergleichenden Modellierung der Proteinstruktur", Journal of Molecular Biology , 279 (1): 287–302, doi : 10.1006/jmbi.1998.1689 , PMID 9636717.
Sethuraman, Samyukta; Butenko, Sergiy (2015), "The maximum ratio clique problem", Computational Management Science , 12 (1): 197–218, doi : 10.1007/s10287-013-0197-z , MR 3296231 , S2CID 46153055.
Song, Y. (2015), „On the Independent set problem in random graphs“ , International Journal of Computer Mathematics , 92 (11): 2233–2242, doi : 10.1080/00207160.2014.976210 , S2CID 6713201.
Spirin, Viktor; Mirny, Leonid A. (2003), "Proteinkomplexe und funktionelle Module in molekularen Netzwerken", Proceedings of the National Academy of Sciences , 100 (21): 12123–12128, Bibcode : 2003PNAS..10012123S , doi : 10.1073/pnas. 2032324100 , PMC 218723 , PMID 14517352.
Tarjan, RE ; Trojanowski, AE (1977), "Finding a maximum Independent Set" (PDF) , SIAM Journal on Computing , 6 (3): 537–546, doi : 10.1137/0206038.
Tomita, E.; Kameda, T. (2007), "Ein effizienter Branch-and-Bound-Algorithmus zum Finden einer maximalen Clique mit Computerexperimenten", Journal of Global Optimization , 37 (1): 95–111, doi : 10.1007/s10898-006-9039 -7 , S2CID 21436014.
Tomita, E.; Seki, T. (2003), "Ein effizienter Branch-and-Bound-Algorithmus zum Finden einer maximalen Clique" , Discrete Mathematics and Theoretical Computer Science , Lecture Notes in Computer Science, 2731 , Springer-Verlag, S. 278–289 , doi : 10.1007/3-540-45066-1_22 , ISBN 978-3-540-40505-4.
Tomita, E.; Tanaka, A.; Takahashi, H. (2006), "The Worst-Case Time Complexity for Generating all Maximum Cliques and Computational Experiments", Theoretical Computer Science , 363 (1): 28–42, doi : 10.1016/j.tcs.2006.06.015.
Tsukiyama, S.; Ide, M.; Ariyoshi, I.; Shirakawa, I. (1977), "Ein neuer Algorithmus zur Erzeugung aller maximalen unabhängigen Mengen", SIAM Journal on Computing , 6 (3): 505–517, doi : 10.1137/0206036.
Valiant, LG (1983), "Exponentielle Untergrenzen für eingeschränkte monotone Schaltungen", Proc. 15. ACM Symposium on Theory of Computing , S. 110–117, doi : 10.1145/800061.808739 , ISBN 0-89791-099-0, S2CID 6326587.
Wassilewska, V. ; Williams, R. (2009), „Gewichtete Teilgraphen finden, minimieren und zählen“, Proc. 41. ACM Symposium on Theory of Computing , S. 455–464, CiteSeerX 10.1.1.156.345 , doi : 10.1145/1536414.1536477 , ISBN 978-1-60558-506-2, S2CID 224579.
Wegener, I. (1988), "On the Complexity of Branching Programs and Decision Trees for Clique Functions", Journal of the ACM , 35 (2): 461–472, doi : 10.1145/42282.46161 , S2CID 11967153.
Yuster, R. (2006), "Finden und zählen von Cliquen und unabhängigen Mengen in r -uniform hypergraphs", Information Processing Letters , 99 (4): 130–134, doi : 10.1016/j.ipl.2006.04.005.
Zuckerman, D. (2006), "Linear Degree Extractors and the Inapproximability of max Clique and chromatic number", Proc. 38. ACM-Symp. Theory of Computing , S. 681–690, doi : 10.1145/1132516.1132612 , ISBN 1-59593-134-1, S2CID 5713815 , ECCC TR05-100.

Languages

In other projects