Vertex Cover

Vertex Cover (kurz VC) ist ein Graphproblem, bei dem es darum geht, mit Knoten Kanten abzudecken.

Für einen Graphen $G=(V,E)$ ist eine Menge $V'\subseteq V$ gesucht, für die gilt:

$\forall (a,b)\in E:a\in V'\lor b\in V'$

In seiner Entscheidungsvariante übergibt man ausser den Graphen noch einen Parameter k und es ist zu entscheiden, ob es ein Vetex Cover dieser Kardinalität gibt. Die Lösung ist nicht unbedingt eindeutig.

In der Optimierungsvariante ist ein VC mit minimaler Kardinalität gesucht.

Das Problem ist NP-vollständig.

Beispiel:

Graph:

    *
   /
*-*
|/|
*-*

einige mögliche Vertex Cover (Die Knoten aus dem Vertex Cover sind mit 'o' gekennzeichnet):

    *
   /
*-o
|/|
o-*
    *
   /
o-o
|/|
o-*
    o
   /
o-*
|/|
o-o
    o
   /
o-o
|/|
o-o