für einen ungerichteten Graphen G = (V, E) eine Knotenmenge V′ so, daß für jede Kante \(\{v,w\}\in E\) mindestens einer der Knoten in V′ enthalten ist.

Beim vertex cover-Problem besteht die Aufgabe darin, ein vertex cover minimaler Größe zu berechnen. Die Entscheidungsvariante (Entscheidungsproblem) ist NP-vollständig. Es gibt einen approximativen Algorithmus, der in polynomieller Zeit eine worst case-Güte von 2 (Güte eines Algorithmus) erreicht.