Вычислительная сложность оптимального блокирования вершин в орграфе

В настоящей работе решена задача определения минимального набора ребер, удаление которых из орграфа разрывает все пути, проходящие через выделенное множество вершин. Эта задача сведена к задаче о минимальном разрезе и максимальном потоке в двухполюснике. Предложены способы декомпозиции орграфа, уменьшающие вычислительную сложность алгоритма решения данной задачи.