Remova o número mínimo de vértices para desconectar o gráfico

Considere um gráfico não direcionado com uma fonte e um vértice de coletor. Gostaríamos de remover o número mínimo de vértices nesse gráfico para desconectar qualquer caminho entre a origem e o coletor.

Podemos fazer isso usando, por exemplo, um algoritmo de fluxo máximo e min-cut?

(Essa resposta foi originalmente fornecida como parte da pergunta, com o objetivo de ser verificada.)

Minha intuição me diz que podemos usar o algoritmo max-flow e min-cut para resolver esse problema:

1. Substitua cada uma das arestas não direcionadas por um par de arestas direcionadas.
2. Substitua cada vértice pelos dois vértices e conectados por uma aresta. todas as arestas de serão conectadas com , todas as arestas de saída de serão conectadas com .$v$$v_\text{in}$$v_\text{out}$$v$$v_\text{in}$$v$$v_\text{out}$
3. Tente encontrar um corte mínimo . As arestas de referem aos vértices que precisamos remover.$M$$M$