Устойчивость в задаче поиска минимального разреза в графе

Задача комбинаторной оптимизации называется устойчивой, если ее решение сохраняется при возмущении входных параметров, не превышающих некоторого порогового значения — радиуса устойчивости. В работах [1–3], в предположении об устойчивости входа, построены точные полиномиальные алгоритмы для некоторых NP-трудных задач о разрезах.
В настоящей работе показано, как строить ускоренные алгоритмы для достаточно устойчивых полиномиальных задач. Подход иллюстрируется на примере известной задачи о минимальном разрезе (MINCUT). Построен $O(n^2)$ точный алгоритм решения $n$-устойчивой задачи MINCUT. Кроме того, построен полиномиальный алгоритм вычисления радиуса устойчивости задачи MINCUT и получен простой критерий $n$-устойчивости.