Том 29, номер 1, 2022 г., Стр. 5-17
УДК 519.8+518.25
Ворошилов В. В.
Сложность задачи о максимальном разрезе с условием минимального доминирования
Аннотация:
Пусть $G = (V,E,w)$ — простой взвешенный неориентированный граф с неотрицательными весами рёбер. Пусть $D$ — минимальное доминирующее множество вершин в $G$. Разрез, порождённый множеством $D$, — это множество рёбер, один из концов которых принадлежит $D$, а другой — $V$ \ $D$. Весом разреза является сумма весов принадлежащих ему рёбер. Данная работа посвящена поиску разреза максимального веса среди всех минимальных доминирующих множеств в неориентированном графе. В частности, доказывается несуществование приближённого полиномиального алгоритма с гарантированной точностью, лучшей чем $|V|^{-\frac{1}{2}}$, в случае $P\ne NP$.
Ил. 3, библиогр. 8.
Ключевые слова: граф, разрез, доминирующее множество, взвешенный граф, задача оптимизации, аппроксимация.
DOI: 10.33048/daio.2022.29.706
Ворошилов Владимир Владимирович 1
1. Омский гос. университет им. Ф. М. Достоевского,
пр. Мира, 55а, 644077 Омск, Россия
е-mail: voroshil@gmail.com
Статья поступила 19 февраля 2021 г.
После доработки — 1 декабря 2021 г.
Принята к публикации 2 декабря 2021 г.
Литература
[1] Симанчёв Р. Ю., Уразова И. В., Ворошилов В. В., Карпов В. В., Кораблёва А. А. Выбор системы ключевых показателей экономической безопасности региона с использованием модели (0, 1)-программирования // Вестн. Омск. гос. ун-та. Сер. Экономика. 2019. Т. 17, № 3. С. 170–179.
[2] Cheston G. A., Fricke G., Hedetniemi S. T., Jacobs D. P. On the computational complexity of upper fractional domination // Discrete Appl. Math. 1990. V. 27, No. 3. P. 195–207.
[3] Boria N., Della Croce F., Paschos V. Th. On the max min vertex cover problem // Discrete Appl. Math. 2015. V. 196. P. 62–71.
[4] Ворошилов В. В. Разрез наибольшего веса в орграфе, порождённый минимальным доминирующим множеством // Дискрет. анализ и исслед. операций. 2020. Т. 27, № 4. С. 5–20.
[5] Кристофидес Н. Теория графов. Алгоритмический подход.М.: Мир, 1978.
[6] Karp R. M. Reducibility among combinatorial problems // Complexity of Computer Computations. Proc. Symp. (New York, USA, March 20–22, 1972). New York: Plenum Press, 1972.
[7] Lee J., Nagarajan V., Shen X. Max-cut under graph constraints // Integer Programming and Combinatorial Optimization. Proc. 18th Int. Conf. (Liège, Belgium, June 1–3, 2016). Cham: Springer, 2016. P. 50–62 (Lect. Notes Comput. Sci.; V. 9682).
[8] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
