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

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.