Knotenüberdeckung

Teilmenge der Knotenmenge eines Graphen, die von jeder Kante mindestens einen Endknoten enthält

Eine Knotenüberdeckung bezeichnet in der Graphentheorie eine Teilmenge der Knotenmenge eines Graphen, die von jeder Kante mindestens einen Endknoten enthält. Das Finden von kleinsten Knotenüberdeckungen gilt als algorithmisch schwierig, denn das damit eng verwandte Knotenüberdeckungsproblem ist NP-vollständig.

Definitionen

Bearbeiten
 
Zwei (nichtminimale) Knotenüberdeckungen.
 
Zwei minimale Knotenüberdeckungen.

Sei   ein ungerichteter Graph mit der Knotenmenge   und der Kantenmenge  . Dann ist eine Teilmenge   eine Knotenüberdeckung (englisch Vertex Cover) von  , wenn jede Kante von   wenigstens einen Knoten aus   enthält. Entsprechend dazu ist eine Kantenüberdeckung des Graphen eine Teilmenge   seiner Kantenmenge, so dass jeder Knoten in mindestens einer Kante aus   enthalten ist.

Eine Knotenüberdeckung   von   nennt man minimal, wenn es keinen Knoten   gibt, so dass   ohne   immer noch eine Knotenüberdeckung ist. Gibt es in   keine Knotenüberdeckung, die weniger Elemente als   enthält, so nennt man   eine kleinste Knotenüberdeckung. Die Anzahl der Knoten einer kleinsten Knotenüberdeckung von   nennt man Knotenüberdeckungszahl von  .

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

Bearbeiten
  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 doppelt so groß sein wie die Paarungszahl, da die Knoten aller Paarungskanten eine gültige Knotenüberdeckung ergeben.
  3. In bipartiten Graphen stimmen Knotenüberdeckungszahl und Paarungszahl überein. (Satz von König)

Probleme und Komplexität

Bearbeiten

Das Entscheidungsproblem zu einem Graphen   und einer natürlichen Zahl   zu entscheiden, ob   eine Knotenüberdeckung der Größe höchstens   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.

Nachweis der NP-Schwere

Bearbeiten

Das Knotenüberdeckungsproblem ist NP-vollständig, das zugehörige Optimierungs- und Suchproblem ist NP-äquivalent. 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. Das Knotenüberdeckungsproblem gehört zur Liste der 21 klassischen NP-vollständigen Probleme, von denen Richard Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte.

In Polynomialzeit lösbare Fälle

Bearbeiten

Der ungarische Mathematiker Dénes Kőnig konnte schon 1931 zeigen, dass in bipartiten Graphen die Knotenüberdeckungszahl der Paarungszahl entspricht (Satz von König). 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. Tatsächlich gilt sogar etwas stärker, dass die Knotenüberdeckungszahl in perfekten Graphen in polynomieller Zeit berechnet werden kann.

Approximation einer Knotenüberdeckung

Bearbeiten

Es existiert ein Approximationsalgorithmus, der eine Knotenüberdeckung mit relativer Güte 2 berechnet. Es ist kein besserer Algorithmus mit fester Güte bekannt.

Der Algorithmus berechnet eine nicht-erweiterbare Paarung   in  . 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 relativer Güte 2.

 : Graph
approx_vertex_cover( ) 1   2 solange  : 3 wähle eine beliebige Kante   4   5 entferne alle Kanten aus  , die inzident zu   oder   sind 6 return  

Der Algorithmus hat bei einer geeigneten Datenstruktur eine Laufzeit von  .

Bearbeiten

Literatur

Bearbeiten