Due in class Friday, April 10th.
Show that the following problems are NP-complete. To do this, you may use any of the NP-complete problems we have discussed in class.
1. Given two graphs and and an integer , determine whether they have a common subgraph with at least edges.
2. A cycle cover of an undirected graph is a set of disjoint simple cycles that cover all vertices of the graph, with each vertex on exactly one cycle. Given a graph and an integer , determine whether the graph has a cycle cover with at most cycles.
3. Given a graph and an integer , determine whether there exists a subset S of at most vertices such that every vertex is either in S or adjacent to some vertex in S.