User daniele - MathOverflow 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 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 Comment by Daniele 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 Comment by Daniele 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 Comment by Daniele 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 Comment by Daniele 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.