Сложность задачи о максимальном разрезе с условием минимального доминирования

Пусть $G=(V,E,w)$  — простой взвешенный неориентированный граф с неотрицательными весами рёбер. Пусть $D$  — минимальное доминирующее множество вершин в $G.$ Разрез, порождённый множеством $D,$  — это множество рёбер, один из концов которых принадлежит $D,$ а другой  — $V\setminus D.$ Весом разреза является сумма весов принадлежащих ему рёбер. Данная работа посвящена поиску разреза максимального веса среди всех минимальных доминирующих множеств в неориентированном графе. В частности, доказывается несуществование приближённого полиномиального алгоритма с гарантированной точностью, лучшей чем $|V|^{-\frac{1}{2}},$ в случае $\text{P}\ne\text{NP}.$ Ил. 3, библиогр. 8.