Supprimer le nombre minimum de sommets pour déconnecter le graphique

Considérons un graphe non orienté avec une source et un sommet récepteur. Nous aimerions supprimer le nombre minimum de sommets dans ce graphique pour déconnecter tout chemin entre la source et le récepteur.

Pouvons-nous le faire en utilisant, par exemple, un algorithme max-flow et min-cut?

(Cette réponse a été initialement donnée dans le cadre de la question, dans le but de la vérifier.)

Mon intuition me dit que nous pouvons utiliser un algorithme max-flow et min-cut pour résoudre ce problème:

1. Remplacez chacun des bords non orientés par une paire d'arêtes dirigées.
2. Remplacez chaque sommet par deux sommets v in et v out reliés par une arête. tous les bords entrants de v seront connectés avec v in , tous les bords sortants de v seront connectés avec v out .$v$$v_\text{in}$$v_\text{out}$$v$$v_\text{in}$$v$$v_\text{out}$
3. Essayez de trouver une coupe minimum . Les bords de M se réfèrent aux sommets que nous devons supprimer.$M$$M$