Es sei G = ( V , E ) {\displaystyle {}G=(V,E)} ein Graph. Eine Teilmenge W ⊆ V {\displaystyle {}W\subseteq V} heißt Knotenüberdeckung von G {\displaystyle {}G} , wenn jede Kante mindestens einen Knoten aus W {\displaystyle {}W} trifft.
