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
Longest path
Moderator: Board moderators
"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.
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.
-
Juergen Werner
- New poster
- Posts: 27
- Joined: Wed Apr 17, 2002 7:54 pm
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.
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="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.
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.