Das Knotenüberdeckungsproblem (oft mit VERTEX COVER notiert) ist ein Problem der Graphentheorie. Es fragt, ob zu einem gegebenen einfachen Graphen und einer natürlichen Zahl k eine Knotenüberdeckung der Größe von höchstens k existiert. Das heißt, ob eine aus maximal k Knoten bestehende Teilmenge U der Knotenmenge gibt, sodass jede Kante des...