Show that the following three problems are polynomial time reducible to each other.

Set-Cover: Given a collection of sets, and a number k, the Set-Cover problem asks if there are at most k sets from the collection of sets such that their union contains every element in the union of all sets.

Hitting-Set: Given a collection of sets, and a number k, the Hitting-Set problem asks if are there at most k elements of the sets such that there is at least one element from each set?

Dominating-Set: Given an undirected graph G, and a number k, the Dominating-Set problem asks if there is a subset of vertices of size k such that every vertex in the graph is either in the subset or has a neighbor that is in the subset.

Prove Set-Cover, Hitting-Set and Dominating-Set are polynomial-time reducible to each other.

(Hint: One strategy is to show Set-Cover p Hitting-Set, Hitting-Set _p Dominating-Set and Dominating-Set _p Set-Cover. An alternative way is to show Hitting-Set _p Dominating-Set, Dominating-Set _p Hitting-Set, Set-Cover _p Dominating-Set and Dominating-Set _p Set-Cover. In class we have seen Vertex-Cover reduced poly to Dominating-Set).