Problem pokrycia wierzchołkowego

Problem pokrycia wierzchołkowego – zagadnienie znajdowania w danym grafie $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 $k.$

Definicja formalna

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

Problem pokrycia wierzchołkowego przedstawiony formalnie:

$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 $GRAPHS$ jest zbiorem grafów, $V_{G}$ – zbiorem wierzchołków grafu $G,$ a $E_{G}$ – zbiorem krawędzi grafu $G.$

Status

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