) -Algorithmus für das K-Clique-Problem

Das Cliquenproblem ist ein bekanntes -vollständiges Problem, bei dem die Größe der erforderlichen Clique Teil der Eingabe ist. Das k-Clique-Problem hat jedoch einen trivialen polynomialen Zeitalgorithmus ( O ( n k ), wenn k konstant ist). Ich interessiere mich für die bekanntesten oberen Schranken, wenn k konstant ist.$NP$$O(n^k)$$k$

Gibt es einen Algorithmus mit der Laufzeit ? A o ( n k ) -Zeit - Algorithmus ist ebenfalls akzeptabel. Gibt es auch eine komplexitätstheoretische Konsequenz für die Existenz solcher Algorithmen?$O(n^{k-1})$$o(n^k)$

Eine 3-Clique kann in einem Vertex-Graphen G in der Zeit O ( n ω ) , wobei ω < 2.376 der Matrixmultiplikations-Exponent ist, und im O ( n 2 ) -Raum durch ein Ergebnis von Itai und Rodeh gefunden werden. [1] . Grundsätzlich zeigen sie, dass G genau dann ein Dreieck enthält, wenn ( A ( G ) ) 3 auf seiner Hauptdiagonale einen Eintrag ungleich Null hat. Denn ein Dreieck ist auch ein Zyklus C $n$$G$$O(n^\omega)$$\omega < 2.376$$O(n^2)$$G$$(A(G))^3$$C_3$kann man allgemeine Zyklenfindungsmethoden zum Erkennen von Dreiecken verwenden. Alon, Yuster und Zwick zeigen, wie Dreiecke in einem Eck-Graphen in der Zeit O ( m 2 ω / ( ω + 1 ) ) = O ( m 1,41 ) detektiert werden können [6].$m$$O(m^{2\omega/(\omega+1)}) = O(m^{1.41})$

Das Ergebnis von Nesetril und Poljak war lange Zeit das bekannteste; Sie zeigten, dass die Anzahl der Cliquen mit einer Größe von in den Zeiträumen O ( n ω k ) und O ( n 2 k ) gefunden werden kann. Schließlich verbesserten Eisenbrand und Grandoni [3] das Ergebnis von Nesetril und Poljak für eine ( 3 k + 1 ) -Klasse und eine ( 3 k + 2 ) -Klasse für kleine Werte von k . Insbesondere gaben sie Algorithmen zum Auffinden von Cliquen der Größen 4, 5 und 7 in der Zeit $3k$$O(n^{\omega k})$$O(n^{2k})$$(3k+1)$$(3k+2)$$k$ , O ( n 4,220 ) bzw. O ( n 5,714 ) .$O(n^{3.334})$$O(n^{4.220})$$O(n^{5.714})$

Soweit ich weiß, ist für allgemeines das Problem offen, bessere Algorithmen zu entwerfen. Für mögliche Folgen oder komplexitätstheoretischen Überlegungen, Downey und Fellows (siehe zB [4]) zeigte k -clique mit Parametern k heißt W [ 1 ] -hard. Die Klasse W [ 1 ] bezeichnet die Klasse der parametrisierten Entscheidungsprobleme, die mit parametrisierten Reduktionen auf CLIQUE reduzierbar sind. Es wird angenommen, dass CLIQUE nicht über festgelegte Parameter gesteuert werden kann. Es sind Hunderte anderer Probleme bekannt, die CLIQUE bei parametrisierten Reduzierungen entsprechen. Darüber hinaus haben Feige und Kilian [5, Abschnitt 2] das Ergebnis, dass, wenn $k$$k$$k$$W[1]$$W[1]$$k$Ist ein Teil der Eingabe und , dann ist es unwahrscheinlich, dass ein Polyzeitalgorithmus existiert.$k \approx \log n$

Wenn Sie einige eingeschränkte Diagrammklassen berücksichtigen, können Sie das Problem in linearer Zeit auf Akkorddiagrammen lösen. Berechnen Sie einfach einen Clique-Baum eines Akkordgraphen in O ( n + m ) und überprüfen Sie dann, ob eine Clique genau k groß ist . Auf ebenen Graphen kann man mit den Methoden von [6] auch Dreiecke in O ( n ) -Zeit finden.$G$$O(n+m)$$k$$O(n)$

[1] Itai, Alon und Michael Rodeh. "Finden einer minimalen Schaltung in einem Graphen." SIAM Journal on Computing 7.4 (1978): 413 & ndash; 423.

[2] Nešetřil, Jaroslav und Svatopluk Poljak. "Über die Komplexität des Subgraph-Problems." Commentationes Mathematicae Universitatis Carolinae 26.2 (1985): 415 & ndash; 419.

[3] Eisenbrand, Friedrich und Fabrizio Grandoni. "Über die Komplexität von Clique mit festen Parametern und dominierender Menge." Theoretical Computer Science 326.1 (2004): 57 & ndash; 67.

[4] Downey, RG und Michael R. Fellows. "Grundlagen der parametrisierten Komplexität." Undegradierte Texte in der Informatik, Springer-Verlag (2012).

[5] Feige, Uriel und Kilian, Joe. "On Limited versus Polynomial Nondeterminism". Chicago Journal of Theoretical Computer Science. (1997)

[6] Alon, Noga, Raphael Yuster und Uri Zwick. Msgstr "Bestimme und zähle gegebene Längenzyklen." Algorithmica 17.3 (1997): 209 & ndash; 223.