Re: [igraph] Longest path algorithm in igraph?

[Tamas Nepusz]

> I know that the longest path problem is NP-complete, but I was
> wondering whether there exist any approximate optimization techniques
> (like, for instance, on modularity maximization for community
> detection, which is also NP-complete).
There are approximation techniques for this problem, e.g.:

Karger et al: On approximating the longest path in a graph. Algorithmica
18(1):82-98, 1997.

> As a matter of fact, I am interested in determining pairs of
> vertices (let's say in a simple undirected graph) which are joined
> together by (possibly multiple) paths having the same length (and
> finding this unique path length for each pair of such vertices).
I'm not sure I understand completely what you mean; do you mean that you are
looking for a pair of vertices (u, v) such that all the *simple* paths from
u to v (simple meaning that it may pass through any vertex only once) are of
equal length (and this would be achieved by checking whether the length of
the shortest path from u to v is the same as the length of the longest path
from u to v)?

-- 
T.