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 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} : \exist V \subseteq V_G, \forall e \in E_G, \exist v \in V : v \in e \ \and \ 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.