Re: [igraph] All paths between all existing nodes of a network

[jordi torrents]

2010/4/14 Gábor Csárdi <address@hidden>:
> On Wed, Apr 14, 2010 at 11:42 AM, jordi torrents <address@hidden> wrote:
>> As Tamas points out, finding all the paths is not possible if the
>> graphs contains cycles. However, if you restrict the search to
>> node-independent paths (which is a known NP-hard problem), there is an
>> approximation algorithm developed by White and Newman [1] which gives
>> good lower bounds on numbers of node-independent paths between any
>> pair of nodes.
>
> Maybe I am missing something, but I don't think this is an NP-complete
> problem. You can solve it in polynomial time, using maximum flow
> techniques. igraph has a function that gives you the maximum number of
> vertex-independent paths:
> igraph.sourceforge.net/doc/html/igraph_vertex_disjoint_paths.html

Gábor,

I think you are right. I've thought that the problem was NP-hard
because the working paper that I cited in my previous mail [1] says
so.  I've found the reference to [1] in [2] (which I've discovered
recently). I guess that [1] is just an obsolete working paper.

Salut!

[1] Fast approximation algorithms for finding node-independent paths in networks
http://eclectic.ss.uci.edu/~drwhite/working.pdf

[2] The Cohesiveness of Blocks in Social Networks: Node Connectivity
and Conditional Density
http://www.jstor.org/stable/3097280