Удалить минимальное количество вершин, чтобы отключить граф

Рассмотрим неориентированный граф с источником и вершиной стока. Мы хотели бы удалить минимальное количество вершин в этом графе, чтобы разъединить любой путь между источником и приемником.

Можем ли мы сделать это, используя, скажем, алгоритм максимального потока, минимального разреза?

(Этот ответ был первоначально дан как часть вопроса, с целью его проверки.)

Моя интуиция подсказывает мне, что мы можем использовать алгоритм максимального потока, минимального разреза для решения этой проблемы:

1. Замените каждый из ненаправленных ребер парой направленных ребер.
2. Замените каждую вершину двумя вершинами и соединенными ребром. все входящие ребра будут связаны с , все исходящие ребра будут связаны с .$v$$v_\text{in}$$v_\text{out}$$v$$v_\text{in}$$v$$v_\text{out}$
3. Попробуйте найти минимальный разрез . Ребра относятся к вершинам, которые нам нужно удалить.$M$$M$