The Minimum$-$Cost Dominating Set Problem is specified by an undirected graph G $=($V$,$ E$)$ and costs c$($v$)$ on the nodes v in V$.$ A subset S $$ V is said to be a dominating set if all nodes u in V$$S have an edge $($u$,$ v$)$ to a node v in S$.($Note the difference between dominating sets and vertex covers: in a dominating set, it is fine to have an edge $($u$,$ v$)$ with neither u nor v in the set S as long as both u and v have neighbors in S$.)$

Give a polynomial$-$time algorithm for the Dominating Set Problem for the special case in which G is a tree.

For this Problem refers to$,$ the$$Maximum$-$Weight$$Independent$$Set Problem on a Tree.$$Noted the difference$$between$$Dominate$$Set and Vertex Cover Set. Hence, for a no$-$leaf node u$,$ if u is in$,$ its children can be either in or out; if u is out, then one of the two following cases must be true: a$.$u$\text{'}$s$$parent node is in ; b$.$ at least one of$$u$\text{'}$s$$children nodes is in$.$

a$)$First describe the overall idea of the algorithm using English language. b$)$Then present the algorithm details using pseudo code, be clear of the meaning of each variable, with comments on important steps to explain its purpose.

c$)$Must$$walk through the algorithm step by step with a small problem instance to show how the algorithm works.

d$)$Analyze time complexity of algorithm and present results in big$-$O notation.