Copertura dei vertici

In teoria dei grafi, si dice copertura dei vertici o copertura tramite vertici (in inglese vertex cover) o copertura per nodi, un sottoinsieme $S$ dei nodi di un grafo $G=(V,E)$ tale che tutti gli archi in $E$ abbiano almeno un estremo in $S$ . Il problema di determinare la più piccola copertura tramite vertici di un grafo (detto problema di copertura dei vertici) è un noto problema di ottimizzazione, studiato in teoria della complessità come esempio di problema NP-completo.