Re: [igraph] Longest path algorithm in igraph?

[Moses Boudourides]

Thank you Tamas,

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

In any case, I should say that part of my problem is not so general
and perhaps you may be able to suggest to me another idea to deal with
it. 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). In
other words, this is the case when geodesic paths are also maximal
length paths. Notice that I'd also like to include the degenerate case
of closed paths (of length larger or equal to three) between a vertex
and itself, i.e., cycles passing from a vertex. In this particular
case, I'm interested in determining vertices from which at most one
cycle might pass (and the period of these cycles).

My motivation for this computation is to be able to formulate problems
of transitivity (local clustering, small-worldedness, structural holes
etc.) in a more formal way (graph-theoretically) than in the existing
approaches.

Any clues?

Best,

--Moses


On Sat, Jul 16, 2011 at 7:11 PM, Tamás Nepusz <address@hidden> wrote:
> Is there an algorithm computing longest paths in graphs implemented in
> igraph or elsewhere?
>
> Not in igraph, unless the graph is acyclic, in which case you can succeed
> with negating the edge weights and finding the shortest path. If the graph
> is directed and acyclic, you may also use the topological sorting algorithm
> which achieves the same. Otherwise, as far as I know, the problem is
> NP-hard, and there is no implementation for solving this problem in igraph.
> Best,
> Tamas
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>