Exercises

 

1. Prove that the vertex cover problem (does there exist a subset S of k vertices in a graph G such that every edge in G is incident upon at least one vertex in S?) remains NP-complete even when all the vertices in the graph are restricted to have even degree.

2. An instance of the set cover problem consists of a set X of n elements, a family F of subsets of X, and an integer k. The question is, do there exist k subsets from F whose union is X?

   For example, if and , there does not exist a solution for k=2 but there does for k=3 (for example, ).

   Prove that set cover is NP-complete with a reduction from vertex cover.

3. The baseball card collector problem is as follows. Given packets , each of which contains a subset of that year's baseball cards, is it possible to collect all the year's cards by buying packets?

   For example, if the players are and the packets are

   

   there does not exist a solution for k=2 but there does for k=3, such as

   

   Prove that the baseball card collector problem is NP-hard using a reduction from vertex cover.

4. (*) An Eulerian cycle is a tour that visits every edge in a graph exactly once. An Eulerian subgraph is a subset of the edges and vertices of a graph that has an Eulerian cycle. Prove that the problem of finding the number of edges in the largest Eulerian subgraph of a graph is NP-hard. (Hint: the Hamiltonian circuit problem is NP-hard even if each vertex in the graph is incident upon exactly three edges.)

5. The low degree spanning tree problem is as follows. Given a graph G and an integer k, does G contain a spanning tree such that all vertices in the tree have degree at most k (obviously, only tree edges count towards the degree)? For example, in the following graph, there is no spanning tree such that all vertices have degree less than three.

   

   1. Prove that the low degree spanning tree problem is NP-hard with a reduction from Hamiltonian path.
   2. Now consider the high degree spanning tree problem, which is as follows. Given a graph G and an integer k, does G contain a spanning tree whose highest degree vertex is at least k? In the previous example, there exists a spanning tree of highest degree 8. Give an efficient algorithm to solve the high degree spanning tree problem, and an analysis of its time complexity.
6. (*) The problem of testing whether a graph G contains a Hamiltonian path is NP-hard, where a Hamiltonian path P is a path that visits each vertex exactly once. There does not have to be an edge in G from the ending vertex to the starting vertex of P, unlike in the Hamiltonian cycle problem.

   Given a directed acyclic graph G (a DAG), give an O(n+m)-time algorithm to test whether or not it contains a Hamiltonian path. (Hint: think about topological sorting and DFS.)

7. (**) The 2-SAT problem is, given a Boolean formula in 2-conjunctive normal form (CNF), decide whether the formula is satisfiable. 2-SAT is like 3-SAT, except that each clause can have only two literals. For example, the following formula is in 2-CNF:

   

   Give a polynomial-time algorithm to solve 2-SAT.

8. (*) It is an open question whether the decision problem ``Is integer n a composite number, in other words, not prime?" can be computed in time polynomial in the size of the input. Why doesn't the following algorithm suffice to prove it is in P, since it runs in O(n) time?

   
   
   PrimalityTesting(n)
   
   		composite :=   
   
   		for i := 2 to n-1 do
   
   				     if    then
   
   						           composite :=