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.

Improve this question
$\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

Reset to default
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.

Improve this answer
$\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$
    – Jérôme JEAN-CHARLES
    Jul 4, 2019 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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