Найти минимальный разрез в графе так, чтобы заданные вершины были несвязными

Некоторое время назад я прочитал об общем алгоритме mininum cut, который принимает на вход граф и удаляет минимальное количество ребер так, что остаются две несмежные компоненты.

Сейчас я работаю над неориентированным графом с 10k+ вершинами и 500k+ ребрами (без кратных ребер между двумя вершинами). Для атрибуции взаимодействий между вершинами я думал о вычислении минимального разреза, разъединяющего две заданные вершины (или меры, связанной с потоком).

Существуют ли эффективные алгоритмы, позволяющие получить значение (кардинальность минимального множества разрезов) для каждой пары вершин в графе? Будучи довольно новичком в этой теме, я буду глубоко признателен, если кто-нибудь предоставит ссылки на статьи или другие ресурсы, описывающие алгоритмы, которые работают при разумной сложности времени выполнения.

Спасибо!