Problembeschreibung

Beim Vertex-Cover-Problem gilt es, für einen gegebenen Graphen G=(V, E) eine Knotenmenge V' zu finden, die Teilmenge von V ist und deren Größe einen gegebenen Wert k nicht überschreitet, so daß für jede Kante in E gilt, daß wenigstens eines ihrer Enden in V' ist.