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 minimal, wenn W ∖ { w } {\displaystyle {}W\setminus \{w\}} zu jedem w ∈ W {\displaystyle {}w\in W} keine Knotenüberdeckung ist.
