Question

A subset of the nodes of a graph is a dominating set if every other node of is adjacent to some node in the subset. Let

$\mathbf{\backslash (}\mathbf{\backslash )}$

localid="1663236390542" $$\begin{gathered} \mathbf{\backslash }\mathbf{t}\mathbf{e}\mathbf{x}\mathbf{t}\mathbf{\{}\mathbf{D}\mathbf{O}\mathbf{M}\mathbf{I}\mathbf{N}\mathbf{A}\mathbf{T}\mathbf{I}\mathbf{N}\mathbf{G}\mathbf{-}\mathbf{S}\mathbf{E}\mathbf{T}\mathbf{\}}\mathbf{=}\mathbf{\backslash }\mathbf{\{}\mathbf{l}\mathbf{a}\mathbf{n}\mathbf{g}\mathbf{l}\mathbf{e}\mathbf{G}\mathbf{,}\mathbf{k}\mathbf{\backslash }\mathbf{r}\mathbf{a}\mathbf{n}\mathbf{g}\mathbf{l}\mathbf{e}\mathbf{\backslash }\mathbf{m}\mathbf{i}\mathbf{d}\mathbf{G}\mathbf{\backslash }\mathbf{t}\mathbf{e}\mathbf{x}\mathbf{t}\mathbf{\{}\mathbf{h}\mathbf{a}\mathbf{s}\mathbf{a}\mathbf{d}\mathbf{o}\mathbf{m}\mathbf{i}\mathbf{n}\mathbf{a}\mathbf{t}\mathbf{i}\mathbf{n}\mathbf{g}\mathbf{s}\mathbf{e}\mathbf{t}\mathbf{w}\mathbf{i}\mathbf{t}\mathbf{h}\mathbf{\}}\mathbf{k}\mathbf{\backslash }\mathbf{t}\mathbf{e}\mathbf{x}\mathbf{t} \\ \mathbf{\left\{}\mathbf{n}\mathbf{o}\mathbf{d}\mathbf{e}\mathbf{s}\mathbf{\right\}}\mathbf{\backslash }\mathbf{\}} \end{gathered}$$

$\mathbf{\backslash (}\mathbf{\backslash )}$

Show that it is $\mathit{N}\mathit{P}$-complete by giving a reduction from VERTEX-COVER.

Short answer

$DOMINATING-SETisNP-complete.$

Step-by-step solution

To Check node and Polynomial time

$DOMINATING-SET$is in :

Consider an instance$\$\backslash langle G,k\backslash rangle\$$ of the$DOMINATING-SET$ and a covering $D$.

Check that each node of$G$ is adjacent to some node in $D$.

This can be done in polynomial time.

Therefore, $DOMINATING-SET$is in $NP$.

$VERTEX-COVER\$\backslash leq\_\left\{mathrm\right\{p\left\}\right\}\$DOMINATING-SET$

Now show that $VERTEX-COVER$ reduces to $DOMINATING-SET$.

To Consider an instance angle

Consider an instance $\$langle(V,E),k\backslash rangle\$$of$VERTEX-COVER$

Construct an instance$\$\backslash left\backslash langle\backslash left\left(\right(V-S)\backslash cupV^\{\backslash prime\},E\backslash cupE^\{\backslash prime\}\backslash right,k\backslash right\backslash rangle\$$

of $DOMINATING-SET$where$\$S\backslash subseteqV\$$ are nodes of degree 0 .

For each edge $\$(u,v)$\in , there are edges$\$(u,w)\$$ and$\$(w,v)\{\backslash text\{in\left\}\right\}E^\{\backslash prime\}\$$ where $\$w\backslash inv^\left\{prime\right\}\$$in new vertex corresponding torole="math" localid="1663233233403" $(u,v)$

$$\begin{gathered} Let\$G=\backslash langleV,E\backslash rangle\$and\$G^\{\backslash prime\}=\backslash left\backslash langle(V-S)\backslash cupV^\{\backslash prime\},E\backslash cup \\ E^\{\backslash prime\}\backslash right\backslash rangle\$ \end{gathered}$$

Suppose$\$(\backslash langleV,E\backslash rangle,k)\$$is in$VERTEX-COVER$ .

There exits $\$C\backslash subseteqV\$$of size$k$ where each edge $\$(u,v)\backslash inE\{\backslash text\{haseither\left\}\right\}u\backslash inE\{\backslash text\{haseither\left\}\right\}u\backslash inC\$or\$V\backslash inC\$$.

If $\$v\backslash i(V-S)\$$then the degree of$v$ is one or more then there exists a node $u$such that$\$(u,v)\backslash in E\$$ which implies that at least one of $u$or$v$ is in $C$. Thus, $v$is covered.

To Implies at least one

If$\$w\backslash inV^\{\backslash prime\}\$then\$\backslash mathrm\left\{w\right\}\$$is adjacent to both$u$and $v$where$\$(u,v)\backslash inE\$$which implies that at least one of$u$or$v$ is in$C$ . Thus, is covered.

In other direction, suppose that$\$\backslash left\backslash langle\backslash left\left(\right(V-S)\backslash cupV^\{\backslash prime\},E\backslash cupE^\{\backslash prime\}\backslash right),$$k\backslash right\backslash rangle\$$is in $DOMINATING-SET$.

Then there exists $\$C\backslash subseteq\backslash left\left(\right(V-S)\backslash cupV^\{\backslash prime\}\backslash right)\$$of size $k$.

In such cases in which multiple such $\$C\$$exist, it can be said that at least one includes no vertices in $\$V^\left\{prime\right\}\$$.

This is always exists since $\$w\backslash in\backslash left(C\backslash capV^\{\backslash prime\}\backslash right)\$$that corresponds to edge $\$(u,v)\$$covers only nodes $u,v,w$but using instead of w Covers and possibly more.

Therefore, $\$C\backslash subseteq(V-S)\$$and $\$C\$$is a vertex cover for $G$.

This is because $C$is a$DOMINATING-SET$ for implying that all nodes ofare $\$V^\{\backslash prime\}\$$covered. Thus, every edge$\$(u,v)\backslash inE\{\backslash text$ {has at least one of }$u,v\}\$$ in$\$c\$$.

$DOMINATING-SET$is $NP$-complete.