1
$\begingroup$

To solve the min dominating set problem of a graph G, we can reduce it to a set cover problem.

For example to find the MDS of the graph G:

G

We can create an instance of the Set Cover problem by:

  1. Introducing the universe U to be equal to all vertices of the graph: U={0, 1, 2, 3, 4}.

  2. For every closed neighborhood of a vertex in G, we introduce a subset S:

    s= {{0, 1}, {0, 1, 2}, {1, 2, 3, 4}, {2, 3, 4}, {2, 3, 4}}

A minimum set cover solution of the instance (s, U) is similar to a minimum dominating set solution in the graph G.

My first question is how we can prove that this reduction is correct, and will give the correct MDS solution for every graph. In our example, the reduction works well and give the correct result.

My second question is how this reduction is related to the reduction when we deal with NP-complete proof(for example we can prove that the MDS problem is NP-complete by reduction to the vertex cover problem).

Are those reductions related? Thank you

$\endgroup$
1
$\begingroup$

Let $G$ be an instance of dominating set and construct an instance of $(U,\mathcal{S})$ of set cover as you describe. The claim is that $G$ has a dominating set of size $k$ if and only if there is a subfamily $\mathcal{S}' \subseteq \mathcal{S}$ with $k$ members that covers $U$.

In the first direction, which you indicate is clearer, let $D$ be a dominating set of size $k$. Construct $\mathcal{S'}$ by adding into it the set corresponding to the closed neighborhood of every $v \in D$. Clearly, $\mathcal{S}'$ has size $k$ as $D$ has size $k$. Further, by the definition of a dominating set, $\mathcal{S}'$ also covers $U$.

In the second direction, let $\mathcal{S}'$ be a set cover for $U$. Build $D$ such that if the set $S_v$, the set corresponding to the closed neighborhood of $v$, is in $\mathcal{S}'$, add the vertex $v$ to $D$. Because $\mathcal{S}'$ covers $U$ which by construction corresponds to the vertex set of $G$, we have that $D$ is a dominating set. Moreover, we clearly have that $D$ has size $k$ as $\mathcal{S}'$ has size $k$.

Your second question however is unclear. A reduction "being related to another reduction" is not a formal statement. In an informal sense, you can use similar ideas to establish other reductions between dominating set, set cover and/or vertex cover but you have to work through the details yourself.

$\endgroup$
  • $\begingroup$ If we want to prove that some problem A is NP-complete, we can prove that by a reduction to another problem B, where B is NP-complete. But in my first question we are dealing with a solution to a problem, and not a NP-complete proof by reduction. My question was if those two reduction equivalent, is there some relation. $\endgroup$ – zak zak May 24 at 14:40
  • 1
    $\begingroup$ @zakzak No, that is wrong. To show that X is hard you must reduce from an NP-complete problem A to X, not the other way around. I precisely gave you a polynomial-time reduction in my answer: the reduction is the construction that you described, and my answer is the correctness proof. $\endgroup$ – Juho May 24 at 14:56
  • $\begingroup$ @zakzak Don't worry, it's surprisingly easy to get the direction of the reduction wrong but it happens less often with a lot of practice :-) $\endgroup$ – Juho May 24 at 15:10

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.