Note: An isomorphism f from graph G to graph H is a one-to-one, onto function from the vertices of G to the vertices of H such that, for every pair of vertices {u,v} of G, {u,v} is an edge in G if and only if {f(u),f(v)} is an edge in H. Graphs G and H are isomorphic if there is an isomorphism from G to H.

Note: Before working each problem, try an example of the problem so that you see what is being asked.

1. The Subgraph isomorphism problem is as follows.

   Input: Two undirected graphs G and H, where G has at least as many vertices as H.

   Question: Does there exist a subgraph of G that is isomorphic to H? That is, can you take a subset of the vertices and a subset of the edges of G, and get a graph that is isomorphic to H?

   Hint: There is no known polynomial time algorithm to test whether two undirected graphs are isomorphic, so don't assume that there is one. Reduce from the clique problem or the hamilton cycle problem.

2. The Hitting set problem is as follows.

   Input: Finite set S, a list C of subsets of S and a positive integer k.

   Question: Does there exist a subset H of S having k members such that every subset in list C contains at least one member of H?

   Hint: Reduce from vertex cover.

3. The Largest common subgraph problem is as follows.

   Input: Two undirected graphs G and H, and a positive integer k.

   Question: Does there exist a graph that has k vertices and that is isomorphic to a subgraph of G and also to a subgraph of H? That is, can the same graph (up to isomorphism) of k vertices be obtained from both G and H by deleting zero or more vertices and edges?

   Hint: Reduce from either clique or hamilton cycle.

4. The Course scheduling problem is as follows.

   Input: A list of courses; a list of pairs of courses, where each pair (c_i,c_j) indicates that there is a student who wants to take both courses c_i and c_j; and a positive integer k indicating the number of time slots available.

   Question: Is there a way to assign time slots to courses so that every student can take his or her desired courses, without any time conflicts? That is, can the courses be scheduled so that, if (c_i,c_j) is in the list of pairs, then courses c_i and c_j are not assigned the same time slot?

   Hint: Reduce from the graph coloring problem.

5. The 0/1 Knapsack problem is as follows.

   Input: A list of numbers x₁,...,x_n and a positive integer k.

   Question: Does there exist a subset I of {1,...,n} such that the sum for all i in I of x_i is exactly k? That is, can you choose some of the numbers from the list x₁,...,x_n so that their sum is k?

   Hint: Reduce from the partition problem.