Prove that MDS is NPC: Minimum dominating set (MDS) Instance: A graph G and an integer k. Question: Does G contain a dominating set of size :E;; k? (It is easy to show that VC cc MDS. Let G' and k...

1. 
   

   
   Prove that
   
   MDS
   
   is
   
   NPC:
   
   

   
   

Minimum dominating set

(MDS)

Instance: A graph

G

and an integer

k.

Question: Does

G

contain a dominating set of size :E;;

k?

(It is easy to show that

VC



cc

MDS.



Let

G'



and

k



be an instance of

VC,

then an instance of

MDS



consists of

G



(constructed from

G'

by adding, for every edge

e,

=

(u,

v) e

G',

a new vertex

x,

and edges

(u,




xj),




(x,,

v)) and k.)