Geodesic
Complexity of the max cut problem with~the~minimal domination constraint
Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 1, pp. 5-17.

Voir la notice de l'article provenant de la source Math-Net.Ru

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\setminus 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 $\text{P}\ne\text{NP}$ is proved. Illustr. 3, bibliogr. 8.
Keywords: graph, cutset, dominating set, weighted graph, optimization problem, approximation. 
@article{DA_2022_29_1_a0,
     author = {V. V. Voroshilov},
     title = {Complexity of the max cut problem with~the~minimal domination constraint},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--17},
     publisher = {mathdoc},
     volume = {29},
     number = {1},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2022_29_1_a0/}
}
TY  - JOUR
AU  - V. V. Voroshilov
TI  - Complexity of the max cut problem with~the~minimal domination constraint
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2022
SP  - 5
EP  - 17
VL  - 29
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2022_29_1_a0/
LA  - ru
ID  - DA_2022_29_1_a0
ER  - 
%0 Journal Article
%A V. V. Voroshilov
%T Complexity of the max cut problem with~the~minimal domination constraint
%J Diskretnyj analiz i issledovanie operacij
%D 2022
%P 5-17
%V 29
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2022_29_1_a0/
%G ru
%F DA_2022_29_1_a0
V. V. Voroshilov. Complexity of the max cut problem with~the~minimal domination constraint. Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 1, pp. 5-17. http://geodesic.mathdoc.fr/item/DA_2022_29_1_a0/

[1] R. Yu. Simanchev, I. V. Urazova, V. V. Voroshilov, V. V. Karpov, 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 (2019), 170–179 (Russian)

[2] Cheston G. A., Fricke G., Hedetniemi S. T., Jacobs D. P., “On the computational complexity of upper fractional domination”, Discrete Appl. Math., 27:3 (1990), 195–207

[3] Boria N., Della Croce F., Paschos V. Th., “On the max min vertex cover problem”, Discrete Appl. Math., 196 (2015), 62–71

[4] V. V. Voroshilov, “A maximum dicut in a digraph induced by a minimal dominating set”, J. Appl. Ind. Math., 14:4 (2020), 792–801

[5] N. Christofides, Graph Theory: An Algorithmic Approach, Academic Press, London, 1975

[6] Karp R. M., “Reducibility among combinatorial problems”, Complexity of Computer Computations, Proc. Symp. (New York, USA, March 20–22, 1972), Plenum Press, New York, 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), Lect. Notes Comput. Sci., 9682, Springer, Cham, 2016, 50–62

[8] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979