Problem pokrycia wierzchołkowego

Problem pokrycia wierzchołkowego

Problem pokrycia wierzchołkowego polega na znalezieniu w grafie $G$ pokrycia wierzchołkowego o najmniejszym rozmiarze, co oznacza minimalną liczbę wierzchołków. Jest to problem optymalizacyjny, jednak w teorii złożoności obliczeniowej częściej rozważa się jego wersję decyzyjną. Ta ostatnia polega na ustaleniu, czy w danym grafie istnieje pokrycie wierzchołkowe o określonym rozmiarze $k.$

Definicja formalna

Formalnie, problem pokrycia wierzchołkowego jest definiowany jako język formalny. Można go przedstawić w następujący sposób:

$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\; text\{card\}\; V\; =\; k\; \},$

gdzie:

• $GRAPHS$ – zbiór grafów,
• $V\_G$ – zbiór wierzchołków grafu $G$,
• $E\_G$ – zbiór krawędzi grafu $G$.

Status problemu

Problem pokrycia wierzchołkowego jest klasyfikowany jako problem NP-zupełny.