Problema di copertura dei vertici: differenze tra le versioni

Nonostante trovare una copertura tramite vertici di cardinalità minima è equivalente a trovare un insieme dominante di cardinalità massima, i due problemi non sono equivalenti in quanto ad approssimabilità. Il problema dell'insieme indipendente non ha approssimazioni a fattori costanti a meno che P=NP

 

* [[covering (graph theory)]]

* [[Hitting set]], una naturale generalizzazione per [[ipergrafi]].