*Problem C has been corrected: It was listed as problem 9, but problem 10
is the correct one.*

- [
*Dominating Sets; 10 points*] A*dominating set*on a graph G is a subset S of nodes such that every node v of G is either in S or is adjacent to at least one node in S. In the*Dominating Set Problem*(*DSP*), you are given a graph G = (V,E) and an integer k, and the goal is to determine if G has a dominating set of size k.

- Give an example of a graph whose smallest dominating set is different
from its smallest vertex cover.

- Show that DSP is NP-complete. [Hint: Try a reduction from 3-SAT, using
3 nodes per variable and one node per clause.]

- Part (2) implies that we don't know of a polynomial-time algorithm for
DSP, but what if the graph is a tree? Give a polynomial-time
algorithm that, given a tree T = (V, E) as input, returns a dominating
set of minimum size.

- Now suppose that every node v has a weight w
_{v}. Give a polynomial-time algorithm that, given a tree T = (V,E) and a weight w_{v}for each node v of T, returns the dominating set of minimum total weight. [Hint: Think*Dynamic Programming*.]

- Give an example of a graph whose smallest dominating set is different
from its smallest vertex cover.
- [
*Loading Trucks (Again); 5 points*] Problem 1 in Chapter 11 of the text.

- [
*Min Weight Independent Set in a Grid Graph; 5 points*] Problem 10 in Chapter 11 of the text.