Разрез наибольшего веса в орграфе, порождённый минимальным доминирующим множеством

Пусть $G=(V,A)$  — простой ориентированный граф с заданными неотрицательными весами дуг, $S\subseteq V$  — некоторое подмножество его вершин. Множество $S$ называется доминирующим, если для каждой вершины $j\in V\setminus S$ существуют как минимум одна вершина $i\in S$ и дуга из $i$ в $j.$ Доминирующее множество называется минимальным по включению, если оно не содержит в себе доминирующих множеств меньшего размера. Разрезом $\overline{S}$ называется множество дуг $(i,j)$ таких, что $i\in S,$ $j\in V\setminus S.$ Весом разреза будем считать суммарный вес входящих в него дуг. В статье исследуется задача поиска разреза $\overline{S}$ максимального веса среди всех минимальных доминирующих множеств $S.$ Ил. 6, библиогр. 8.