Knotenüberdeckungen, Cliquen und stabile Mengen

Knotenüberdeckungen, Cliquen und stabile Mengen sind Begriffe der Graphentheorie und bezeichnen spezielle Teilmengen von Knoten in Graphen. Das Finden von minimalen Knotenüberdeckungen und größten Cliquen bzw. stabilen Mengen gilt als algorithmisch schwierig (NP-vollständig). Da diese Probleme eng miteinander verwandt sind, werden sie in diesem Übersichtsartikel zusammen dargestellt.

Definitionen

Sei GG=(V,E)(V,E) ein ungerichteter Graph ohne Mehrfachkanten und UU eine Teilmenge von VV. Man bezeichnet UU als Clique von GG, wenn für je zwei beliebige verschiedene Knoten vv und ww aus UU gilt, dass sie durch eine Kante miteinander verbunden sind. Gilt hingegen stets für je zwei beliebige verschiedene Knoten vv und ww aus UU, dass sie nicht benachbart sind, so nennt man UU eine stabile bzw. unabhängige Menge (Independent Set) von GG. Enthält jede Kante von EE einen Knoten aus UU, so nennt man UU eine Knotenüberdeckung von GG.
Eine Clique bzw. stabile Menge UU von GG nennt man maximal, wenn man keinen weiteren Knoten vv aus VV zu UU hinzufügen kann, so dass UU zusammen mit vv eine Clique bzw. stabile Menge ist. Gibt es in GG keine Clique bzw. stabile Menge, die mehr Elemente als UU enthält, so nennt man UU größte Clique bzw. größte stabile Menge. Die Anzahl der Elemente einer größten Clique bzw. stabilen Menge nennt man Cliquenzahl bzw. Stabilitäts- oder Unabhängigkeitszahl. Die Anzahl der Knoten einer kleinsten Knotenüberdeckung von GG nennt man Knotenüberdeckungszahl von GG.
Statt über Teilmengen von VV definiert man Cliquen oder stabile Mengen auch als spezielle Teilgraphen.
Als Cliquenüberdeckung von GG der Größe kk bezeichnet man eine Partition der Knotenmenge V(G)V(G) in kk paarweise disjunkte Cliquen V1,V2V_{1},V_{2},...,VkV_{k}.
Gerichtete Graphen oder solche mit Mehrfachkanten sind nicht Gegenstand derartiger Betrachtungen, da es nicht auf die Richtung oder Vielfachheit der Kanten ankommt.

Wichtige Aussagen und Sätze

  1. Die Knotenüberdeckungszahl eines Graphen ist mindestens so groß wie seine Paarungszahl, da die Knoten der Kanten einer größten Paarung nur zu einer Paarungskante inzident sein können.
  2. Andererseits kann die Knotenüberdeckungszahl höchstens so groß sein, wie das 2-fache der Paarungszahl, da die Knoten aller Paarungskanten eine gültige Knotenüberdeckung ergeben.
  3. In bipartiten Graphen stimmen Knotenüberdeckungszahl und Paarungszahl überein.

Probleme und Komplexität

Definition der Probleme

Das Entscheidungsproblem zu einem Graphen GG und einer natürlichen Zahl kk zu entscheiden, ob GG eine Clique der Größe mindestens kk enthält, wird Cliquenproblem genannt. Das zugehörige Optimierungsproblem fragt nach der Cliquenzahl eines Graphen. Das zugehörige Suchproblem fragt nach einer größten Clique. Analog ist das Stabilitätsproblem über stabile Mengen definiert.
Das Entscheidungsproblem zu einem Graphen GG und einer natürlichen Zahl kk zu entscheiden, ob GG eine Knotenüberdeckung der Größe höchstens kk enthält, wird Knotenüberdeckungsproblem genannt. Das zugehörige Optimierungsproblem fragt nach der Knotenüberdeckungszahl eines Graphen. Das zugehörige Suchproblem fragt nach einer kleinsten Knotenüberdeckung. Analog ist das Stabilitätsproblem über stabile Mengen definiert.

Nachweis der NP-Schwere

Alle drei Probleme sind NP-vollständig. Die zugehörigen Optimierungs- und Suchprobleme sind NP-äquivalent. Die NP-Schwere des Stabilitätsproblems lässt sich dabei leicht durch Reduktion des Cliquenproblems auf das Stabilitätsproblem zeigen, indem man den Komplementgraphen bildet. Die NP-Schwere des Knotenüberdeckungsproblems folgt aus dem Satz, dass die Stabilitätszahl eines Graphen immer der Anzahl Knoten eines Graphen abzüglich seiner Knotenüberdeckungszahl entspricht, denn das Komplement einer kleinsten Knotenüberdeckung ist immer eine größte stabile Menge und umgekehrt. Für den Nachweis der NP-Schwere des Cliquenproblems existiert eine Reduktion von 3-SAT auf das Cliquenproblem.

In Polynomialzeit lösbare Fälle

König konnte jedoch schon 1931 zeigen, dass in bipartiten Graphen die Knotenüberdeckungszahl der Paarungszahl entspricht. Für das Problem, eine größte Paarung zu finden, gibt es aber einen polynomiellen Algorithmus. In bipartiten Graphen lässt sich daher auch eine kleinste Knotenüberdeckung und eine größte stabile Menge in polynomieller Zeit berechnen.
Eine größte Clique lässt sich entsprechend der obigen Reduktion in polynomieller Zeit berechnen, wenn der Komplementgraph bipartit ist.
Tatsächlich gilt sogar etwas stärker, dass Cliquenzahl, Stabilitätszahl und Knotenüberdeckungszahl in perfekten Graphen in polynomieller Zeit berechnet werden können. Da die Farbzahl und die Cliquenzahl in solchen Graphen identisch sind, ist auch ihre Farbzahl in polynomieller Zeit berechenbar.
Die Berechnung einer maximalen Clique bzw. stabilen Menge gelingt bereits mit einem einfachen Greedy-Algorithmus.

Approximation einer Knotenüberdeckung

Es existiert ein Approximationsalgorithmus, der eine Knotenüberdeckung mit Güte 2 berechnet. Es ist kein besserer Algorithmus mit fester Güte bekannt.
Der Algorithmus berechnet eine nicht-erweiterbare Paarung M in G. Da eine derartige Paarung immer eine Knotenüberdeckung darstellt und höchstens doppelt so groß ist wie eine minimale Knotenüberdeckung, berechnet der Algorithmus eine Knotenüberdeckung mit Güte 2.
G = (V, E): Graph approx_vertex_cover(G) 1 K ←\leftarrow ∅\varnothing 2 solange E ≠\neq ∅\varnothing: 3 wähle eine beliebige Kante e = {u,v} aus E 4 K ←\leftarrow K ∪\cup {u,v} 5 entferne alle Kanten aus E, die inzident zu u oder v sind 6 return K
Der Algorithmus hat bei einer geeigneten Datenstruktur eine Laufzeit von O(|E|).
 
 

Es ist unglaublich, wie unwissend die studirende Jugend auf Universitäten kommt, wenn ich nur 10 Minuten rechne oder geometrisire, so schläft 1/4 derselben sanft ein.

Georg Christoph Lichtenberg

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Knotenüberdeckungen, Cliquen und stabile Mengen aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Diskrete Mathematik