Graphe bipartite quantité minimale de sommets requis

Question

J'ai un graphique bipartite composé de deux ensembles (SET 1 et SET 2) et je veux déterminer combien de sommets du SET 1 Je peux supprimer tout en ayant chaque sommet du SET 2 connecté à au moins un sommet du SET 1. Dans cet exemple, E et F peut évidemment être supprimé comme D et C est connecté 5 et 6.
Mais nous pourrions aussi supprimer B comme A et C Couvrent ensemble plus de points. Mais jusqu'à présent, je n'ai qu'une implémentation très lente de ceci qui consiste à comparer tous les sommets de SET 1 à chaque combinaison de sommets de SET1.
Y a-t-il un moyen intelligent de le faire? J'ai pensé à Théorème de Kőnig Mais je n'ai pas trouvé de moyen de l'utiliser dans ce contexte car il semble être fait pour des graphiques bipartites non dirigés.

De plus, il y a certaines contraintes que l'entrée suit:
-Tout élément de SET 2 est connecté à SET 1
-Tout nœud de SET 2 est connecté exactement à deux sommets de SET 1