Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
Volume 29, No 1, 2022, P. 5-17
UDC 519.8+518.25
V. V. Voroshilov
Complexity of the max cut problem with the minimal domination constraint
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.
Keywords: graph, cutset, dominating set, weighted graph, optimization problem, approximation.
DOI: 10.33048/daio.2022.29.706
Vladimir V. Voroshilov 1
1. Dostoevsky Omsk State University,
55a Mir Avenue, 644077 Omsk, Russia
e-mail: voroshil@gmail.com
Received February 19, 2021
Revised December 1, 2021
Accepted December 2, 2021
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]).
