An instance of the Dominating Set decision problem is a pair $(,),$ where $=(,)$ is a

simple graph, $>=0$ is an integer, and the problem is to decide if $$ has a dominating set of

size $,$ i$.$e$.$ a set $$ for which every vertex $$ in $$ is adjacent to at least one vertex in $.$ For

example, for the graph G shown above, $(,=2)$ is a positive instance of Dominating Set

since D $=\{1,3\}$ is a dominating set for G$.$

a$)$ For a given instance $(,)$ of Dominating Set describe a certificate in relation to $(,).$

b$)$ Provide a semi$-$formal verifier algorithm that takes as input i$)$ An instance $(,)$ ii$)$ a

certificate for $(,)$as defined in part a$,$ and decides if the certificate is valid for $.$

c$)$ Provide size parameters that may be used to measure the size of an instance of

Dominating Set.

d$)$ Use the size parameters from part c to describe the running time of your verifier from

part. Defend your answer in relation to the algorithm you provided for the verifier.