|
Complexity of the max cut problem with the minimal domination constraint
V. V. Voroshilov Dostoevsky Omsk State University, 55a Mir Avenue, 644077 Omsk, Russia
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\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.
Received: 19.02.2021 Revised: 01.12.2021 Accepted: 02.12.2021
Citation:
V. V. Voroshilov, “Complexity of the max cut problem with the minimal domination constraint”, Diskretn. Anal. Issled. Oper., 29:1 (2022), 5–17
Linking options:
https://www.mathnet.ru/eng/da1289 https://www.mathnet.ru/eng/da/v29/i1/p5
|
Statistics & downloads: |
Abstract page: | 176 | Full-text PDF : | 83 | References: | 49 | First page: | 9 |
|