So, I have two problems:Minesweeper: given an undirected graph where some vertices have a whole number associated with them, check if there is a way to mark some of the non-numbered vertices such that the number in each numbered vertex is equal to the amount of its marked neighbours.Dominating set: given an undirected graph and an integer $k$, check if there is a way to mark exactly $k$ vertices such that each non-marked vertex has at least one marked neighbour.I need to construct a polynomial reduction from the second problem to the first (that is, using the solution to the first problem, construct a polynomial solution to the second). I do understand that I will need to add some additional numbered vertices to the graph (because numbering any of the existing vertices will prevent it from being marked). I've tried to add a support vertex for all of the original ones and connect each support vertex to the same vertices, and after that brute-force my way through numbers in each support vertex. The problem is --- that's $O(n^n)$ and definitely not a polynomial.How can I do this in polynomial time?
Reduce Dominating Set to Minesweeper
complexity theory;graphs;reductions