### 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.