Коротко: задача — найти минимальный s–t вершинный разрез (минимальное число вершин, удаление которых разрывает все пути s→t). По теореме Менгера это равно максимуму числа внутренних вершин-несовпадающих (vertex‑disjoint) путей s→t, и решается через преобразование в реберную задачу потока (vertex‑splitting) + max‑flow.
1) Точное решение (рекомендация)
- Сжать сильно связанные компоненты: найдите SCC (Tarjan/Kosaraju) и замените каждую SCC одной вершиной — это уменьшит граф. Сложность: $O(n+m)$.
- Преобразование вершин в ребра (vertex‑splitting): для каждой вершины $v$ создайте $v_{in}\to v_{out}$ с пропускной способностью $1$ (если считаем стоимость удаления вершины = 1; для весовых вершин поставить вес). Для каждой исходящего ребра $u\to v$ добавьте ребро $u_{out}\to v_{in}$ с «бесконечной» пропускной способностью (поставьте большое $INF$). Для s и t можно не ограничивать пропускную способность (или задать $INF$). Размер преобразованного графа: вершины $\approx 2n$, рёбер $\approx m+n$.
- Решите максимальный поток между $s_{out}$ и $t_{in}$ (максимум потока = минимальный вершинный разрез). Алгоритмы: Dinic, Push‑Relabel (HLPP). Практически: Dinic хорошо для «unit»‑сетей, HLPP (highest label + gap + global relabel) часто быстрее на плотных графах.
- Из остаточной сети найдите достижимые из $s_{out}$ вершины; вершина $v$ принадлежит минимальному вершинному разрезу тогда и только тогда, когда $v_{in}$ достижима, а $v_{out}$ — нет. (Исключая s,t по договорённости.)
- Сложности: построение и SCC — $O(n+m)$. Теоретически Dinic имеет худший предел $O(V^{2}E)$, но для единичных/малых пропускных способностей часто оценивают как $O(E\sqrt{V})$ в практике; push‑relabel имеет худший предел больший, но на практике очень быстры. Для ваших размеров ($n$ до $10^5$) это обычно выполнимо при разумном $m$ (до сотен тысяч — миллиона рёбер) и оптимизированной реализации.
2) Альтернативные/дополнительные методы
- Поиск $k$ вершинных непересекающихся путей напрямую: если ожидаемый ответ мал (малое $k$), можно искать поочередно $k$ путей методом DFS/BFS с блокировкой внутренних вершин; сложность $O(k(n+m))$. Это часто быстрее, если минимум мал.
- Доминирующая вершина / доминаторное дерево: алгоритм Ленгауэра–Тарджана ($O(n+m)$) даёт вершины, которые лежат на всех путях s→v. Если вершина доминирует t, то она обязательно в разрезе (особенно полезно для обнаружения единичных разрезов).
- Сжатие в DAG (конденсация SCC): анализ конденсированного DAG даёт возможность быстро искать критические перегородки между компонентами (это упрощает задачу, если граф «сильно связанный» внутри компонент).
- Для неориентированного графа стандартно используют поиск точек сочленения (articulation points) и мостов — $O(n+m)$. Для ориентированного графа аналог — анализ SCC и доминаторов.
3) Практические эвристики для больших графов
- Предобработка: удалите вершины, не достижимые из s и/или не достижимые к t (две BFS), так уменьшается граф; сложность $O(n+m)$.
- Сжать SCC — часто радикально уменьшает размер.
- Если нужна только «малая» разрезка или приближённое решение: жадные эвристики — удалять вершины с наибольшим центральностью (betweenness, degree), либо многократно искать поток/пути и собирать вершины, покрывающие все найденные пути (approx‑set‑cover). Такие эвристики не гарантируют оптимум, но дают быстрые приближения.
- Ограничение итераций maxflow (ранняя остановка), если достаточно знать, что разрез ≥ K, и дальнейшая точность не нужна.
- Использовать оптимальные библиотеки (исходники Dinic/HLPP на C++), компактное хранение (adjacency lists, int32), и большое значение $INF$ как $10^9$ или больше, но в пределах типа.
- Параллельные/распределённые решения и внешняя память — при очень больших $m$ (>10^7) применять специализированные инструменты.
4) Рекомендованный рабочий пайплайн
- Удалить недостижимые вершины (BFS/DFS из s и обратный из t).
- Сжать SCC.
- Сконструировать vertex‑split граф (capacity = 1 для внутренних вершин).
- Запустить max‑flow (Dinic для разреженных/единичных графов, HLPP для тяжёлых случаев).
- Из остаточной сети извлечь минимальный набор вершин по достижимости.
- При больших данных или необходимости скорости: сначала попытаться greedy/DFS‑based поиск k путей, или использовать приближённые эвристики.
Если нужно — могу дать псевдокод для vertex‑splitting + Dinic и код извлечения вершин разреза.