CS4123 Theory of Computation 
Homework 4 - D 2002

PROF. CAROLINA RUIZ 

Due Date: Friday, April 26th at 3 pm. 
Help session: Thursday, April 25th, 3:00-4:15 p FL232
Late Policy: No late homework will be accepted

Problems

1. (20 points) Consider the Edge Cover problem:
   • Given: A graph G=(V,E), and a positive integer k.
   • Output: "Yes", if there is a subset E' of E with |E'| <= k such that for each vertex v in V there is some egde e in E' that has v as one of its end-points. "No", otherwise

   Show that this problem is in the class P. That is, show that there is a deterministic Turing machine that decides this problem in polynomial time in the size of the input.

   ---

2. (20 points) Consider the Shortest path between two vertices problem:
   • Given: A graph G=(V,E); a posive cost c(e) for each edge e in E; specified vertices a and b in V; and a positive integer B.
   • Output:"Yes", if there is a simple path from a to b in G having total cost less than or equal to B. "No", otherwise.

   Note that a simple path is one that doesn't visit a vertex more than once; and the cost of a path is the sum of the cost of each edge in the path.

   Show that this problem is in the class P. That is, show that there is a deterministic Turing machine that decides this problem in polynomial time in the size of the input.

   ---

3. (40 points) Consider the Longest path between two vertices problem:
   • Given: A graph G=(V,E); a posive cost c(e) for each edge e in E; specified vertices a and b in V; and a positive integer B.
   • Output:"Yes", if there is a simple path from a to b in G having total cost greater than or equal to B. "No", otherwise.
   1. (20 points) Show that this problem is in the class NP.
   2. (20 points) Show that this problem is NP-complete.

   ---

4. (40 points) Consider problem 7.26 in the textbook (p. 274).
   1. (20 points) Show that this problem is in the class NP.
   2. (20 points) Show that this problem is NP-complete.

Additional Problem for Students taking the course for Graduate Credit

Homework Submission

You can submit this homework assignment in any of the following ways. Make sure you hand it in BY 3 pm on Friday, April 26th.
• by handing in your solutions during class on Friday, April 26th.
• by handing in your solutions during John's office hour on Friday, April 26th, 2-3 pm.
• by leaving your solutions in my mailbox (CS office FL233). PLEASE MAKE SURE YOU LEAVE YOUR SOLUTIONS IN **MY** MAILBOX (the one UNDER the arrow marked with my lastname RUIZ).