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.

Advertisements

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?

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.

Are the bold problems here https://cs3511.wordpress.com/course-topics/mar-30-np-completeness-and-reductions/ the complete list of problems from class we can reduce to?

Yes.

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

For number 2, are the cycles edge disjoint or vertex disjoint?

Vertex disjoint.

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?