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

Sei ${\displaystyle G=(V,E)}$ ein ungerichteter Graph mit der Knotenmenge ${\displaystyle V}$ und der Kantenmenge ${\displaystyle E}$. Dann ist eine Teilmenge ${\displaystyle U\subseteq V}$ eine Knotenüberdeckung (englisch Vertex Cover) von ${\displaystyle G}$, wenn jede Kante von ${\displaystyle G}$ wenigstens einen Knoten aus ${\displaystyle U}$ enthält. Entsprechend dazu ist eine Kantenüberdeckung des Graphen eine Teilmenge ${\displaystyle M}$ seiner Kantenmenge, so dass jeder Knoten in mindestens einer Kante aus ${\displaystyle M}$ enthalten ist.

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

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 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

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

${\displaystyle G=(V,E)}$: Graph

approx_vertex_cover(${\displaystyle G}$)
1   ${\displaystyle K\leftarrow \varnothing }$
2  solange  ${\displaystyle E\neq \varnothing }$:
3      wähle eine beliebige Kante ${\displaystyle e={u,v}\in E}$
4      ${\displaystyle K\leftarrow K\cup \left\{u,v\right\}}$
5      entferne alle Kanten aus ${\displaystyle E}$, die inzident zu ${\displaystyle u}$ oder ${\displaystyle v}$ sind
6  return ${\displaystyle K}$

Weblinks

Literatur

• Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (diestel-graph-theory.com). 
• Bernhard Korte, Jens Vygen: Kombinatorische Optimierung. Theorie und Algorithmen (= Springer Spektrum). 2. Auflage. Springer, Heidelberg 2012, ISBN 978-3-642-25400-0.