most recent 30 from http://mathoverflow.net 2013-05-20T17:18:29Z http://mathoverflow.net/feeds/user/5059 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/19956/is-this-a-well-known-np-complete-problem Daniele 2010-03-31T15:04:20Z 2010-06-10T08:16:49Z

<p>I came across this problem recently and I wanted to know whether it was a well known NP-complete problem. I checked the library but could not find anything that matched exactly.</p> <p>Given a directed weighted graph G. Find the minimal weight path of length 'n' in the graph. Which is without setting any specific start node or end node.</p> <p>This is not my field, so you will pardon me if the solution is trivial.</p>

http://mathoverflow.net/questions/19956/is-this-a-well-known-np-complete-problem/19961#19961 Daniele 2010-03-31T16:38:55Z 2010-03-31T16:38:55Z

Yes, but this way you are setting $v$ and $w$. While the problem is to find any path of length $n$, without choosing any $v$ or $w$.

http://mathoverflow.net/questions/19956/is-this-a-well-known-np-complete-problem/19961#19961 Daniele 2010-03-31T16:29:33Z 2010-03-31T16:29:33Z

Thanks for your answer. However, how do you find the minimal weight path of length $n$ in $H$? Hasn't the same problem just shifted to $H$?

http://mathoverflow.net/questions/19956/is-this-a-well-known-np-complete-problem Daniele 2010-03-31T15:46:23Z 2010-03-31T15:46:23Z

A path can visit the same node more than once yes. By shortest I meant least weight. By length I meant the number of edges. I think Francois was kind enough to correct the question that now should be clearer. Andrew you are absolutely right that it should be stated as a decision problem. Actually, knowing whether the decision problem lies in NP solve my problem.

http://mathoverflow.net/questions/19956/is-this-a-well-known-np-complete-problem Daniele 2010-03-31T15:12:03Z 2010-03-31T15:12:03Z

Yes it refers to the sum of the weights of the edges on the path of length 'n'. Sorry if that was not clear.