longest path

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
reemuskumar
New poster
Posts: 4
Joined: Wed Jun 14, 2006 3:55 pm

longest path

Post 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

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post 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.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post 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 ;) ]

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post 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. :)

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post 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.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post 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.

Moheeb
New poster
Posts: 21
Joined: Fri May 05, 2006 9:08 am
Location: Dhaka ,Bangladesh

Post 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.

Moheeb
New poster
Posts: 21
Joined: Fri May 05, 2006 9:08 am
Location: Dhaka ,Bangladesh

Post 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.

Post Reply

Return to “Algorithms”