Page 1 of 1

longest path

Posted: Wed Jul 26, 2006 3:47 pm
by reemuskumar
Hi all,

I'm tring to solve 103 Box Stacking problem. I have a graph representation of the boxes in adjacency list.

Is there is any good algorithm to find the longest path ? (any reference)

Thanks,
Reemus Kumar

Posted: Wed Jul 26, 2006 4:16 pm
by Cosmin.ro
If the graph is acyclic then you can do it by topological sort. If it is not then the problem is NP.

Posted: Wed Jul 26, 2006 4:58 pm
by misof
Cosmin.ro: NP-what? :)

The correct phrase here would be "is known to be NP-hard", meaning:
- if we were able to solve this problem in polynomial time, we would be able to solve any problem from NP in polynomial time
- it is not even known whether there is a non-deterministic polynomial algorithm for this problem

[No offense intended, of course... It's just that I've been TAing a formal languages course for several years, so one can imagine I get a bit upset when people misuse the notation ;) ]

Posted: Wed Jul 26, 2006 5:37 pm
by Per
misof wrote:Cosmin.ro: NP-what? :)

The correct phrase here would be "is known to be NP-hard", meaning:
- if we were able to solve this problem in polynomial time, we would be able to solve any problem from NP in polynomial time
- it is not even known whether there is a non-deterministic polynomial algorithm for this problem
Wouldn't the correct phrase actually be, "is known to be FNP-hard", since it's a function problem? And the second point is not implied by the NP/FNP-hardness, as you seem to indicate.
misof wrote:[No offense intended, of course... It's just that I've been TAing a formal languages course for several years, so one can imagine I get a bit upset when people misuse the notation ]
I agree with you here an all points. :)

Posted: Wed Jul 26, 2006 10:35 pm
by misof
Hehe, I got what I asked for :D

The clarifications are in place, of course. The intended formulation was "the problem is NP-hard and we don't know whether it is NP-complete". My second point is just the translation of "we don't know whether it is NP-complete" into words.

As of the other point, even the decision problem (given a graph G and an integer K, is K the length of the longest path in G?) is NP-hard.

Posted: Wed Jul 26, 2006 11:05 pm
by Per
Nothing brightens the day up like a little nitpicking. :)

The IMO more standard choice of decision problem for longest path would be "Given G and K, does G have a path of length at least K", which is NP-complete. That is why I dragged in FNP, so that the "not known to be NP-complete" part would stay true.

Posted: Fri Jul 28, 2006 5:58 pm
by Moheeb
Misof wrote:
he intended formulation was "the problem is NP-hard and we don't know whether it is NP-complete".

Sir , i am very poor in English . i don't understand what r u saying ? All
NP-complete problems r NP-hard ,but some NP-hard problems r not
known to be NP-complete .
A problem L is NP-hard if and only if Satisfiability reduces to L.
A problem L is NP-complete if and only if L is NP-hard and L belongs to NP.

Posted: Fri Jul 28, 2006 5:59 pm
by Moheeb
Misof wrote:

he intended formulation was "the problem is NP-hard and we don't know whether it is NP-complete".

Sir , i am very poor in English . i don't understand what r u saying ? All
NP-complete problems r NP-hard ,but some NP-hard problems r not
known to be NP-complete .
A problem L is NP-hard if and only if Satisfiability reduces to L.
A problem L is NP-complete if and only if L is NP-hard and L belongs to NP.