Reduce Dominating Set to Minesweeper

Question

So, I have two problems:

1. 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.

2. 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?

Answer 1

Given an instance $(G, k)$ of DOMINATING SET, we construct our instance of MINESWEEPER as follows.

• Add a new vertex $s$, connect $s$ with all the vertices of $V(G)$. Label $s$ with $k$.
• For each $v\in V(G)$, add a new vertex $s_v$. Connect $s_v$ to all the vertices of $N(v)\cup\{v\}$ (the neighborhood of $v$ and $v$ itself). Connect $s_v$ to $|N(v)| - 1$ new dummy vertices. Label $s_v$ with $|N(v)|$.

Call the constructed graph $G'$. The produced MINESWEEPER instance is $G'$ itself.

We claim that $(G, k)$ is a YES instance of DOMINATING SET iff. $G'$ is a YES instance of MINESWEEPER.

Proof: If $(G, k)$ is a YES instance of DOMINATING SET, we have a dominating set $S\subseteq V(G)$ with $|S| = k$. By simply marking all the vertices of $S$, we satisfy the label of $s$ in $G'$. Then, for each $s_v\in V(G')$, according to the number of marked vertices (up to now) in $N(v)\cup\{v\}$, we mark some of the dummy vertices connected with $s_v$. Note that, since $S$ is dominating, $N(v)\cup\{v\}\cap S\neq\emptyset$, so at most $|N(v)|-1$ dummy vertices needs to be marked to satisfy the label of $s_v$, so we always have enough number of dummy vertices connected to $s_v$.

Conversely, if $G'$ is a YES instance of MINESWEEPER, we denote by $S$ the non-dummy vertices (which also means that these are in $V(G)$) in the solution to this instance. We now show that $S$ is a dominating set of $G$ and $|S|=k$, which concludes our proof. Indeed, to satisfy the label of $s$, we have that $|S|=k$. For each vertex $s_v$, at most $|N(v)|-1$ dummy vertices connected to it are marked. So in order to satisfy its label, namely $|N(v)|$, either $v$ or some vertex in $N(v)$ is marked. So, in particular, if $v$ is not marked, i.e. $v\not\in S$, there must be some marked vertex in $N(v)$, i.e. $N(v)\cap S\neq\emptyset$. This suffices to prove that $S$ is a dominating set of $G$.$\square$