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 gesucht, für die gilt:

In seiner Entscheidungsvariante übergibt man außer den Graphen noch einen Parameter k und es ist zu entscheiden, ob es ein Vertex 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

Beispiel

Der erste Graph ist der Ursprungsgraph. Die anderen sind jeweils ein Vertex Cover, wobei die eingekreisten Knoten die Knoten aus V' (aus dem Vertex Cover) sind. Das erste Vertex Cover (also der zweite Graph) ist hierbei ein minimales Vertex Cover.