Usuń minimalną liczbę wierzchołków, aby rozłączyć wykres

Zastanów się nad niekierowanym wykresem ze źródłem i wierzchołkiem ujścia. Chcemy usunąć minimalną liczbę wierzchołków na tym wykresie, aby odłączyć dowolną ścieżkę między źródłem a ujściem.

Czy możemy to zrobić, używając algorytmu maksymalnego przepływu, minimalnego cięcia?

(Ta odpowiedź została pierwotnie podana jako część pytania, w celu weryfikacji).

Moja intuicja mówi mi, że możemy użyć algorytmu maksymalnego przepływu, minimalnego cięcia, aby rozwiązać ten problem:

1. Zastąp każdą z nieukierunkowanych krawędzi parą skierowanych krawędzi.
2. Zamień każdy wierzchołek $v$ z dwoma wierzchołkami $v_\text{in}$ i $v_\text{out}$połączone krawędzią. wszystkie przychodzące krawędzie$v$ będzie związany z $v_\text{in}$, wszystkie wychodzące krawędzie $v$ będzie związany z $v_\text{out}$.
3. Spróbuj znaleźć minimalne cięcie $M$. Krawędzie$M$ odnoszą się do wierzchołków, które musimy usunąć.