Knotenüberdeckung

Definitionen

Sei G=(V,E) ein ungerichteter Graph ohne Mehrfachkanten und U eine Teilmenge von V. Man bezeichnet U als Clique von G, wenn für je zwei beliebige verschiedene Knoten v und w aus U gilt, dass sie durch eine Kante miteinander verbunden sind, d.h. benachbart (Graphentheorie) sind. Gilt hingegen für je zwei beliebige verschiedene Knoten v und w aus U, dass sie nicht benachbart sind, so nennt man U eine stabile Menge von G. Enthält jede Kante von E einen Knoten aus U, so nennt man U eine Knotenüberdeckung von G.

Eine Clique bzw. stabile Menge U von G nennt man maximal, wenn man keinen weiteren Knoten v aus V zu U hinzufügen kann, so dass U zusammen mit v eine Clique bzw. stabile Menge ist. Gibt es in G keine Clique bzw. stabile Menge, die mehr Elemente als U enthält, so nennt man U größte Clique bzw. größte stabile Menge. Die Anzahl Elemente einer größten Clique bzw. stabilen Menge nennt man Cliquenzahl bzw. Stabilitäts- oder Unabhängigkeitszahl. Die Anzahl Knoten einer kleinsten Knotenüberdeckung von G nennt man Knotenüberdeckungszahl von G.

Statt über Teilmengen von V definiert man Cliquen oder stabile Mengen auch als spezielle Teilgraphen.

Als Cliquenüberdeckung von G der Größe k bezeichnet man eine Partition der Knotenmenge V(G) in k paarweise disjunkte Cliquen V₁,V₂,...,V_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

Das so genannte Cliquenproblem, also das Problem in einem Graphen eine größte Clique bzw. stabile Menge zu finden, ist NP-schwer, d. h. es gibt aus Sicht der Komplexitätstheorie vermutlich keinen effizienten Algorithmus, der das Problem in angemessener Zeit löst. Durch Bildung des Komplementgraphen kann man leicht das eine Problem in das andere überführen. Das Cliquenproblem lässt sich polynomial reduzieren auf 3-SAT.

Man kann leicht zeigen, dass die Stabilitätszahl eines Graphen immer der Anzahl Knoten eines Graphen abzüglich seiner Knotenüberdeckungszahl entspricht. Damit folgt unmittelbar, dass es auch NP-schwer ist, eine kleinste Knotenüberdeckung zu finden.

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.