6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Dominating_set ​ ​ $\endgroup$ – user12859 Sep 23 '16 at 19:30
  • $\begingroup$ Are you after a Karp or a Cook reduction? $\endgroup$ – Raphael Sep 23 '16 at 20:03
  • $\begingroup$ @Raphael We haven't actually covered different types of reductions yet, so I assume that I need a Cook reduction, because it's the least restrictive (right?) $\endgroup$ – Akiiino Sep 23 '16 at 20:07
  • 3
    $\begingroup$ Right. I'm asking because "using the solution to the first problem, construct a polynomial solution to the second" fits Cook but not Karp. Karp is, however, kind of the default in the context of NP-completeness because NP-hardness is defined using Karp reductions. $\endgroup$ – Raphael Sep 23 '16 at 20:21
2
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.