Problem pokrycia wierzchołkowego

Problem pokrycia wierzchołkowego – zagadnienie znajdowania w danym grafie ${\displaystyle G}$ pokrycia wierzchołkowego o najmniejszym rozmiarze, tj. zawierającego możliwie najmniejszą liczbę wierzchołków. Tak zdefiniowany problem pokrycia wierzchołkowego jest problemem optymalizacyjnym. W teorii złożoności obliczeniowej częściej jednak rozważa się problemy decyzyjne. Decyzyjna wersja problemu pokrycia wierzchołkowego, to problem stwierdzania czy w danym grafie istnieje pokrycie wierzchołkowe o danym rozmiarze ${\displaystyle k.}$

Problemy decyzyjne definiuje się formalnie jako języki formalne.

Problem pokrycia wierzchołkowego przedstawiony formalnie:

${\displaystyle VC=\{(G,k)\in GRAPHS\times \mathbb {N} :\exists V\subseteq V_{G},\forall e\in E_{G},\exists v\in V:v\in e\ \land \ card\ V=k\},}$

gdzie ${\displaystyle GRAPHS}$ jest zbiorem grafów, ${\displaystyle V_{G}}$ – zbiorem wierzchołków grafu ${\displaystyle G,}$ a ${\displaystyle E_{G}}$ – zbiorem krawędzi grafu ${\displaystyle G.}$

Problem pokrycia wierzchołkowego jest problemem NP-zupełnym.