Bien que le problème de la couverture de poids minimal des sommets soit NP-Complet, Il est possible lorsqu'on
a un graphe biparti de le réduire en temps polynomial à un problème de coupe minimale
dans un réseau de transport[5], connu pour appartenir à 
.