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