Complexity of the max cut Problem with the Minimal Domination Constraint
V. V. Voroshilov · Journal of Applied and Industrial Mathematics · 2022
Let $$ G=(V,E,w) $$ be a simple weighted undirected graph with nonnegative edge weights. Let $$ D $$ be a minimal dominating set in $$ G $$ . The cutset induced by $$ D $$ is the set of edges with one vertex in the set $$ D $$ and the other in $$ V\setminus D $$ . The weight of the cutset is the total weight of all its edges. The paper deals with the problem of finding a cutset with the maximum weight among all minimal dominating sets. In particular, the nonexistence of a polynomial approximation algorithm with a ratio better than $$ |V|^{-\frac {1}{2}} $$ in the case of $$ \text {P} e \text {NP} $$ is proved.