1
$\begingroup$

I was redirected from stackoverflow to ask here.
I want to count a number of all paths between two nodes in graph. The graph can contain cycles. I have read a lot of articles about this problem but for DAG.

Stackoverflow: Number of paths between two nodes in a DAG

At the moment I have implemented an algorithm to find all paths between two nodes. I can simply count the number of all paths using this algorithm but since it's NP-hard problem, it has ugly time complexity. I am pretty sure I can solve my problem in polynomial time (but do not have a proof for it).

I was thinking about something using adjacency matrix multiplication, i.e. $A^k_{ij}$ is equal to number of paths of length k between nodes i and j, and diameter of graph but I'm getting incorrect result for this.
E.g. for E = {(0, 1), (0, 2), (0, 3), (1, 0), (1, 2), (1, 3), (2, 0), (2, 3), (2, 1), (2, 4), (3, 4), (3, 2), (3, 0), (3, 1), (4, 2), (4, 3)} and V = {0, 1, 2, 3, 4} (simple "house" graph) there are only 7 paths between 0 and 2, but using matrix multiplication and diameter I got only 3 paths. Maybe it's just about misinterpretation of diameter since today it's the first time I have heard of diameter of graph.

Any help would be appreciated.

$\endgroup$
1
  • 1
    $\begingroup$ if the graph can contain cycles, and a cycle is on the path between s and t, shouldn't it contain infinite many paths? $\endgroup$
    – Danyal
    Oct 29, 2020 at 3:34

1 Answer 1

2
$\begingroup$

This is still a hard problem (#P-complete), so it almost certainly can’t be done in polynomial time. See Valiant, L. G. (1979). The Complexity of Enumeration and Reliability Problems. SIAM J. Comput., 8, 410-421.

As for the other part of your question, I wonder if you’ve fallen prey to some terminological confusion. It seems clear that what you’re interested in is counting all the simple paths – paths that visit each node at most once – between two nodes. Multiplying adjacency matrices gives you something different: it counts all the paths, including non-simple ones that may double back on themselves or go round a loop.

$\endgroup$
2
  • $\begingroup$ Sorry, didn't know that actually. $\endgroup$
    – Speedding
    Dec 1, 2017 at 9:14
  • 1
    $\begingroup$ @Robin Yes in fact they are called walks versus paths. For n >= 2 : an n-path has n edges and n+1 vertices, an n-walk has n edges and k vertices ( 1<= k <= n ) . When graph are oriented orientation is assumed implicitly to avoid an heavy "oriented path". When people use path for a walk an alternative to "simple path" could be "pure path". $\endgroup$ Jul 4, 2019 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.