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. Gilt hingegen stets für je zwei beliebige verschiedene Knoten v und w aus U, dass sie nicht benachbart sind, so nennt man U eine stabile bzw. unabhängige Menge (Independent Set) 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.

Probleme und Komplexität

Das Entscheidungsproblem zu einem Graphen G und einer natürlichen Zahl k zu entscheiden, ob G eine Clique der Größe k 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 und das Knotenüberdeckungsproblem durch Knotenüberdeckungen.

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 auf das Cliquenproblem 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 auf 3-SAT.

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.