0
$\begingroup$

How do i show that Double Dominanting Set is NP-Complete by reducing Dominating Set to it i have thought by adding a edge but my solution is not correct

Input is an undirected graph and a target. The question is whether it is possible to find a subset with a maximum vertices that doubly dominate all vertices in the graph. This means that each vertex is either in the subset or has two neighbors that are in the subset. Show that this decision problem is NP-complete by partly showing that it lies in NP and partly by designing a polynomial Karp reduction between the NP-complete problem Dominant Set

$\endgroup$
2
  • 1
    $\begingroup$ Çan you define the problem? $\endgroup$ Jan 9 at 21:24
  • $\begingroup$ Please do no change the question to a different one, especially after receiving an answer. You can instead post a new question. $\endgroup$
    – Steven
    Jan 10 at 17:14

1 Answer 1

1
$\begingroup$

The problem is clearly in $\mathsf{NP}$ (you can use the double dominating set as a yes certificate), and the following reduction shows that it is also $\mathsf{NP}$-Hard.

Given a graph $G = (V,E)$ with $V = \{v_1, \dots, v_n\}$, define $G' = (V', E')$ as the graph obtained by adding $n$ new vertices $v'_1, \dots, v'_n$ along with all edges $(v_i, v'_i)$ for $i=1,\dots,n$.

$G$ has a dominating set of size at most $k$ if and only if $G'$ has a double dominating set of size $k+n$.

Proof: If $S$ is a double dominating set of $G$ of size at most $k$ then $S' = S \cup \{v'_1, \dots,v'_n\}$ has size at most $n+k$ and is a double dominating set of $G'$. Indeed, each vertex $v_i \in V' \setminus S' = V \setminus S$ is dominated by $v'_i$ and by at least one neighbor in $S$.

Conversely, if $S'$ is a dominating set of $G'$ of size at most $n+k$ then $S'$ contains all vertices in $\{v'_1, \dots, v'_n\}$ since each of these vertices only has a single incident edge. Then $S = S' \setminus \{v_1, \dots, v_n\}$ has size at most $k$ and is a dominating set of $G$. Indeed, each $v_i \in V \setminus S$ is dominated by at least two vertices in $S'$ (in the graph $G'$) and, since at most one of these vertices is in $\{v'_1, \dots, v'_n\}$, the others (i.e., at least one) must be in $S$.$\square$

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.