# np complete – How to prove the complexity of this modified version of the minimum dominating set problem? I have an optimization problem and I want to show its complexity. The optimization problem is the same as the minimum dominating set problem, but with an additional constraint. The constraint is easy. Consider a defined subset $$S$$ of nodes in a graph. The additional constraint is to guarantee that at least a given number of nodes in this set are selected. Therefore, I want to find the set $$D$$ with minimum cardinality that ensures all nodes in the graph are dominated and, the given number of nodes in the $$S$$ is selected. Actually, my solution is the union of the solution to the minimum dominating set and the additional constraint. As the cost function is minimizing the cardinality of the solution, so the result to the minimum dominating set should have the most common nodes with the set $$S$$.

I know, the minimum dominating set is a well known NP-Complete problem, and to show the complexity of a problem to an NP-hard or NP-complete I should use polynomial reduction. But, I can’t find a well known NP-hard or NP-complete problem to reduce it to my problem.

Therefore, I want to help me with that, is there any way to find the complexity of my problem? I’m thinking of a way other than reduction.

Or, is there any problem to reduce it to my problem to show its complexity. Posted on Categories Articles