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

## longest path

**Moderator:** Board moderators

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 ]

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: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

I agree with you here an all points.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 ]

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.

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.

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.

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.