Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

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.

This is not my field, so you will pardon me if the solution is trivial.

share|improve this question
    
All paths of length n are equally short, aren't they? They all have length n... –  TonyK Mar 31 '10 at 15:08
1  
Welcome to MO! (Just a very minor nitpick: Using 'shortest' and 'length' with two different meanings in the same sentence tends to be confusing.) –  François G. Dorais Mar 31 '10 at 15:11
5  
The fact that you don't specify the start and end node is irrelevant since if you can do it in polynomial time with a specific pair of nodes then you can do it in polynomial time by checking all $n^2$ pairs of nodes. –  gowers Mar 31 '10 at 15:49
1  
If all the edges have the same length, which you seem to be saying, just take the edge of minimum weight in the whole graph and go along it back and forth n times. –  Mio Mar 31 '10 at 15:53
3  
@Mio - the graph is directed. –  Sam Nead Mar 31 '10 at 16:04

3 Answers 3

The shortest (in terms of weight) path, constrained to have exactly n (or at most n) edges, can be found in polynomial time. For instance, given your graph $G=(V,E)$ make an expanded graph $H$ that has as its vertices the pairs $(v,i)$ where $v\in G$ and $0\le i\le n-1$. Draw an edge in $H$ from $(v,i)$ to $(w,i+1)$ whenever $G$ has an edge from $v$ to $w$, with the same weight. Then the shortest $n$-edge path in $G$ from $v$ to $w$ is the same as the shortest path in $H$ from $(v,0)$ to $(w,n)$. To look for paths in $G$ that are at most $n$ edges long, add to $H$ edges of weight zero from $(v,i)$ to $(v,i+1)$.

However, these paths allow repeated vertices and edges. If repetitions are disallowed, and $G$ has $n+1$ vertices, then the shortest length-$n$ path is just a Traveling salesman path, so of course it's NP-complete.

share|improve this answer
    
That doesn't quite work if you regard non-edges as having weight zero, but even if you do have that convention you can make them into edges with very large weight instead and then the argument works again. –  gowers Mar 31 '10 at 15:55
    
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$? –  Daniele Mar 31 '10 at 16:29
    
You just find the shortest path from (v,0) to (w,n-1). –  rgrig Mar 31 '10 at 16:35
2  
This is polynomial in the size of the graph and n. Can you make it polynomial in the size of the graph and log n? –  aorq Mar 31 '10 at 18:05
1  
I wouldn't be surprised if it were possible to reduce the dependence on n to logarithmic, at some expense in increasing the dependence on the size of the graph. But why would you care? That would only make an improvement when n is much larger than the size of the graph. Do you really care about paths that long? –  David Eppstein Mar 31 '10 at 18:12

The problem of finding the longest path in a graph is NP-complete. (See http://en.wikipedia.org/wiki/Longest_path_problem.) It follows that the problem of determining whether there exists a path of length $k$ is NP-hard (since otherwise you could check all lengths $k$). But then give a huge weight to all non-edges, and your problem is seen to be NP-hard too.

share|improve this answer
1  
Danielle said in a comment that paths are really walks (repeated vertices are allowed). –  rgrig Mar 31 '10 at 17:01
    
AH -- that changes things ... –  gowers Mar 31 '10 at 21:35

This is not even in NP! The input is n, which is of length log(n). But a certificate is of length n, which is exponential compared to log(n). So you can't verify a solution in polynomial time and so it's not in NP.

share|improve this answer
1  
G is part of the input. –  Chad Groft Jun 10 '10 at 10:57
    
We can make n so big that the size of the graph is insignificant. –  Zirui Wang Jun 11 '10 at 11:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.