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

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

Ворошилов В. В.
Дискретный анализ и исследование операций, 29, 1, 5-17 (2022)
Скачать статью

УДК 519.8+518.25 
DOI: 10.33048/daio.2022.29.706

Аннотация:

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

Литература:
  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.
Ворошилов Владимир Владимирович
  1. Омский гос. университет им. Ф. М. Достоевского,
    пр. Мира, 55а, 644077 Омск, Россия

E-mail: voroshil@gmail.com

Статья поступила 19 февраля 2021 г.
После доработки — 1 декабря 2021 г.
Принята к публикации 2 декабря 2021 г.

Abstract:

Let $G = (V,E,w)$ be a simple weighted undirected graph with nonnegative weights of its edges. Let $D$ be a minimal dominating set in $G$. Cutset induced by $D$ is a set of edges with one vertex in the set $D$ and the other in $V$ \ $D$. The weight of a cutset is the total weight of all its edges. The paper deals with the problem of finding a cutset with maximum weight among all minimal dominating sets. In particular, nonexistence of polynomial approximation algorithm with ratio better than $|V|^{-\frac{1}{2}}$ in case of $P\ne NP$ is proved. 
Illustr. 3, bibliogr. 8.

References:
  1. R. Yu. Simanchev, I. V. Urazova, V. V. Voroshilov, V. V. Karpov, and A. A. Korableva, Selection the key indicators system of the region economic security with use of the (0, 1)-programming model, Vestn. Omsk. Univ., Ser. Ekonomika 17 (3), 170–179 (2019) [Russian].
     
  2. G. A. Cheston, G. Fricke, S. T. Hedetniemi, and D. P. Jacobs, On the computational complexity of upper fractional domination, Discrete Appl. Math. 27 (3), 195–207 (1990).
     
  3. N. Boria, F. Della Croce, and V. Th. Paschos, On the max min vertex cover problem, Discrete Appl. Math. 196, 62–71 (2015).
     
  4. V. V. Voroshilov, A maximum dicut in a digraph induced by a minimal dominating set, Diskretn. Anal. Issled. Oper. 27 (4), 5–20 (2020) [Russian] [J. Appl. Ind. Math. 14 (4), 792–801 (2020)].
     
  5. N. Christofides, Graph Theory: An Algorithmic Approach (Academic Press, London, 1975; Mir, Moscow, 1978 [Russian]).
     
  6. R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations (Proc. Symp. CCC, Yorktown Heights, USA, March 20–22, 1972) (Plenum Press, New York, 1972), pp. 85–103.
     
  7. J. Lee, N. Viswanath, and X. Shen, Max-cut under graph constraints, Programming and Combinatorial Optimization (Proc. 18th Int. Conf., Liège, Belgium, June 1–3, 2016) (Springer, Cham, 2016), pp. 50–62 (Lect. Notes Comput. Sci., Vol. 9682).
     
  8. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982 [Russian]).