3

This is the question [From CLRS]:

Define the optimization problem LONGEST-PATH-LENGTH as the relation that associates each instance of an undirected graph and two vertices with the number of edges in a longest simple path between the two vertices. Define the decision problem LONGEST-PATH = {: G=(V,E) is an undirected graph, u,v contained in V, k >= 0 is an integer, and there exists a simple path from u to v in G consisting of at least k edges}. Show that the optimization problem LONGEST-PATH-LENGTH can be solved in polynomial time if and only if LONGEST-PATH is contained in P.

My solution: Given an algorith A, that can solve G(u,v) in polytime, so we run the A on G(u,v) if it returns 'YES" and k' such that k' is the longest path in G(u,v), now all we have to do it compare if 

k =< k'

if then the longest path length is solved. If we recieve "NO" or k>=k', then there exists no solution.

so polytime to run A + constant for comparsion, then to find the longest path length it takes poly time. Also this is only possible since G(u,v) runs in Polytime (in P), thus G(u,v,k) runs also in polytime (in P), therefore since longest path can be reduced to longest-path-length, then longest-path-length is in P.

we can solve it the oposite way, what we do is, run G(u,v,k') for k'=0 to n, every time check if the k==k', is so we solved it. run time analysis for this: n*polytime+ n*(constant comparsion)=polytime

Can someone tell me if my answer is reasonable? if not please tell me where i've gone wrong

Also can you give me some advice to how to study algorithms ,and what approch i should take to solve a algorith question (or a graph question)

please and thankyou

Rave
  • 835
  • 4
  • 15
  • 28
  • 1
    This question belongs on http://cstheory.stackexchange.com/ – Ted Hopp Dec 09 '11 at 04:35
  • You are not fully explaining your notation: What is G(u,v)? What is u and v in that case. What is G(u,v,k)? What is u, v and k in that case? I probably might be able to help you somewhat, but I have no clue on how to read your solution. – LiKao Dec 09 '11 at 10:09
  • 1
    @TedHopp: CSTheory is for research level questions. This is just a textbook problem from Cormen. – hugomg Dec 09 '11 at 12:23

1 Answers1

2

Your answer is reasonable but I would try to shore it up a little bit formally (format the cases separately in a clear manner, be more precise about what polynomial time means, that kind of stuff...)

The only thing that I would like to point out is that in your second reduction (showing the decision problem solves the optimization problem) the for k=0 to N solution is not general. Polynomial time is determined in relation to the length of input so in problems where N is a general number (such as weight or something) instead of a number of a count of items from the input (as in this case) you need to use a more advanced binary search to be sure.

hugomg
  • 68,213
  • 24
  • 160
  • 246