Cliquenproblem - LinkFang.de





Cliquenproblem


Das Cliquenproblem (mit CLIQUE notiert) ist ein Entscheidungsproblem der Graphentheorie. Das Cliquenproblem ist eines der 21 klassischen NP-vollständigen Probleme, deren Zugehörigkeit zu dieser Klasse Richard M. Karp 1972 bewies.

Problemstellung

Es ist gefragt, ob es zu einem einfachen Graphen G und einer Zahl n eine Clique der Mindestgröße n in G gibt; das heißt, ob G zumindest n Knoten hat, die alle untereinander paarweise verbunden sind.

Satz

CLIQUE ist NP-vollständig.

Beweisidee

Polynomialzeitreduktion von 3KNF-SAT auf CLIQUE:

[math]{3KNF-SAT} \preceq_p CLIQUE[/math]

Da 3KNF-SAT NP-schwer ist, gilt dies dann auch für CLIQUE. Außerdem lässt sich leicht zeigen, dass CLIQUE selbst in NP liegt, insgesamt ist es also NP-vollständig.

Beweisskizze

Sei F eine Formel mit n Klauseln in 3KNF, also in konjunktiver Normalform mit höchstens drei Literalen pro Klausel:

[math]F = (y_{1,1} \lor \dotsc \lor y_{1,a_1}) \land \dotsc \land (y_{n,1} \lor \dotsc \lor y_{n,a_n})[/math]
[math]\text{mit}\ \ \forall_{1 \le i \le n} : 1 \le a_i \le 3[/math]
[math]\text{und}\ \ \forall_{i, j} : y_{i,j} \in \{x_1,...,x_m, \overline{x_1},...,\overline{x_m}\}[/math].

Aus F mit n Klauseln konstruieren wir einen Graphen G und zeigen dann: F ist erfüllbar genau dann, wenn G eine n-Clique besitzt.

Konstruktion von G

  • Knoten von G seien sämtliche Literalvorkommen in der Formel F, genauer alle Paare [math](y_{i,j}, i)[/math].
  • Kanten von G seien sämtliche Verbindungen zwischen Literalvorkommen, ausgenommen allein
    1. zwischen zwei Literalvorkommen in ein und derselben Klausel — also nicht [math](y_{i,j_1}, i)[/math] und [math](y_{i,j_2}, i)[/math] per Kante verbinden
    2. zwischen zwei Literalvorkommen, in denen dasselbe Literal einmal positiv und einmal negiert auftritt — also nicht [math](y_{i_1,j_1}, i_1)[/math] und [math](y_{i_2,j_2}, i_2)[/math] verbinden, falls [math]\{y_{i_1,j_1}, y_{i_2,j_2} \} = \{x_k,\overline{x_k}\}[/math] für ein k.

Beweis

  • G besitzt eine n-Clique ⇒ F ist erfüllbar: Angenommen, G besitzt eine n-Clique. Den Literalen [math]y_{i,j}[/math] von in dieser Clique liegenden Literalvorkommen [math](y_{i,j}, i)[/math] geben wir den Wahrheitswert wahr. Dies ist widerspruchslos wegen der 2. Kantenbedingung möglich. Weil nach der 1. Kantenbedingung keine zwei Literalvorkommen aus derselben Klausel per Kante verbunden sind, werden unter dieser Belegung alle n von n Klauseln von F wahr und damit auch F.
  • F ist erfüllbar ⇒ G besitzt eine n-Clique: Angenommen, F sei erfüllbar. Dann gibt es eine Wahrheitswertbelegung seiner Literale, so dass in jeder der Klauseln wenigstens ein Literal wahr wird. Wir wählen in jeder Klausel willkürlich genau ein Literalvorkommen [math](y_{i,j}, i)[/math] mit wahrem [math]y_{i,j}[/math] aus. Alle diese bilden offenbar eine n-Clique in G.

Beispiele

Beispiel für eine erfüllbare Belegung:

[math](\overline{x_1} \lor x_1 \lor \overline{x_2}) \land (x_2 \lor x_1 \lor \overline{x_2}) [/math]

Beispiel für eine nichterfüllbare Belegung:

[math](\overline{x_1} \lor \overline{x_1} \lor x_2) \land (x_2 \lor x_2 \lor x_1)\land (\overline{x_2} \lor \overline{x_2} \lor \overline{x_2})[/math]

Siehe auch

Literatur

  • Schöning, Uwe: Theoretische Informatik - kurzgefasst. - 4. Aufl., korr. Nachdr.. - Heidelberg : Spektrum, Akad. Verl., 2003, ISBN 3-8274-1099-1.

Kategorien: Komplexitätstheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Cliquenproblem (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.