Es sei G = ( V , E ) {\displaystyle {}G=(V,E)} ein Graph. Eine Knotenüberdeckung W ⊆ V {\displaystyle {}W\subseteq V} von G {\displaystyle {}G} heißt optimal, wenn es keine Knotenüberdeckung von G {\displaystyle {}G} mit weniger als # ( W ) {\displaystyle {}{\#\left(W\right)}} Elementen gibt.
