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}:\mathrm{\exists }V\subseteq V_G,\mathrm{\forall }e\in E_G,\mathrm{\exists }v\in V:v\in e\wedge cardV=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.