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.


  1. Do we have to reduce each of the 3 problems to a problem we saw in class? Or can we use the transitive property and reduce one HW problem to another HW problem?


    1. You can reduce between them, but to establish NP-completeness you’ll have to reduce at least one of them to a problem we proved to be NP-complete in class.


      1. Does that mean TSP is allowed? I missed one class but I do not believe that was proved in class.

  2. Can we show that some HW problem reduces to another problem, and then show that that intermediary problem reduces to another problem seen in class?


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s