Page 1 of 1
Longest path
Posted: Tue Nov 05, 2002 12:09 pm
by babe
I have a problem: let G be a graph, G may have circuit, find the longest path in G which go through each vertex at most 1 time and if:
a/ G is directed
b/ G is undirected
Please give me your idea whether a good algorithm exists or not.
Regards,
Babe
Posted: Tue Nov 05, 2002 5:21 pm
by babe
Thank Guest, I think you're right.
But, is there any greedy method?
Regards,
Babe
Posted: Tue Nov 05, 2002 11:55 pm
by zorbathut
"guest". augh. how did it log me in as guest? :P
If it's NP-complete, there's not going to be any greedy method, or indeed, any method at all that runs in less than exponential time. (Okay, this hasn't been *proven* yet, but you're not going to find one :P)
You might be able to come up with a solution that works in the cases you find important (i.e. an input set that isn't "all graphs") or a solution that returns a reasonably good approximation. But unless you've got a less general set of inputs, there's no way you'll come up with an algorithm to do it perfectly and quickly.
Posted: Wed Nov 06, 2002 7:54 pm
by Juergen Werner
I agree with zorbathut, solving the stated problem would solve the Hamilton Path Problem, which is NP-complete.
Discussing this, it might also be interesting to look at a related, yet easy problem: Finding the longest path in an undirected acyclic graph (see 10308 Roads in the North) which can be solved in O(V + E) (V: number of vertices, E: number of edges) using a kind of modified Depth-First Search.
Posted: Thu Nov 07, 2002 4:38 pm
by gilliam
Posted: Fri Feb 21, 2003 8:33 pm
by makbet
[quote="Juergen Werner"]I agree with zorbathut, solving the stated problem would solve the Hamilton Path Problem, which is NP-complete.
Discussing this, it might also be interesting to look at a related, yet easy problem: Finding the longest path in an undirected acyclic graph (see 10308 Roads in the North) which can be solved in O(V + E) (V: number of vertices, E: number of edges) using a kind of modified Depth-First Search.[/quote]
I don't agree that the problem above is NP. Consider this algorithm:
input is u,v - the vertices we are interested in
1. Find longest path ( as you described above )
2. If the two end vertices of the path are u & v exit
3. If one of the vertices of the path is u or v then remove the other one
from the graph, and go to step 1
4. If none of the vertices of the path is u or v then remove both from the
graph and go to step 1
I am just not sure how <step 1> would behave on a graph with cycles,
because I know that the graph from 10308 is a tree.