# HW 5

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 $G_1$ and $G_2$ and an integer $k$, determine whether  they have a common subgraph with at least $k$ 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 $k$, determine whether the graph has a cycle cover with at most $k$ cycles.

3. Given a graph $G = (V, E)$ and an integer $k$, determine whether there exists a subset S of at most $k$ vertices such that every vertex $v \in V$ is either in S or adjacent to some vertex in S.