[Math] Number of paths between two nodes

algorithmsgraph theory

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.

Best Answer

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.

Related Solutions

[Math] Number of paths equal less than equal to a certain length

The problem is and is not NP-hard. If the length of the input is defined by writing the weights in binary, then it is indeed NP-hard and in fact #P-complete. Say that the target weight $W$ is written in base 10. Suppose further that the graph is a string, as in Reid's construction, with two edges from $i$ to $i+1$, one weight 0 and the other with weight some integer in base 10 with only 0s and 1s in its digits. Also, choose all of the weights so that they cannot add together with any carries. Then the $k$th digit $d$ of the target weight $W$ is a Boolean clause, which says that of those edges that have a non-zero $k$th digit, exactly $d$ are used used. It is not hard to build general Boolean circuits with these clauses.

Also, to clarify a couple of points about this: You can convert from weight at most $W$ to weight exactly $W$ by subtracting off weight at most $W-1$; so in this quick argument it is only #P-hard with a Turing reduction and not a Cook reduction. And of course I'm really showing that the knapsack counting problem is #P-hard.

On the other hand, if the length is defined by writing the weights in unary, to favor small integer values of the weights, then the dynamic programming algorithm given in the question is polynomial time.

Which complexity model is more appropriate depends on the context of the problem, which was not given.

[Math] Finding all paths on undirected graph

Suresh suggested DFS, MRA pointed out that it's not clear that works. Here's my attempt at a solution following that thread of comments. If the graph has $m$ edges, $n$ nodes, and $p$ paths from the source $s$ to the target $t$, then the algorithm below prints all paths in time $O((np+1)(m+n))$. (In particular, it takes $O(m+n)$ time to notice that there is no path.)

The idea is very simple: Do an exhaustive search, but bail early if you've gotten yourself into a corner.

Without bailing early, MRA's counter-example shows that exhaustive search spends $\Omega(n!)$ time even if $p=1$: The node $t$ has only one adjacent edge and its neighbor is node $s$, which is part of a complete (sub)graph $K_{n-1}$.

Push s on the path stack and call search(s):

path // is a stack (initially empty)
seen // is a set

def stuck(x)
   if x == t
     return False
   for each neighbor y of x
     if y not in seen
       insert y in seen
       if !stuck(y)
         return False
   return True

def search(x)
  if x == t
    print path
    return
  seen = set(path)
  if stuck(x)
    return
  for each neighbor y of x
    if y not in path:
      push y on the path
      search(y)
      pop y from the path

Here search does the exhaustive search and stuck could be implemented in DFS style (as here) or in BFS style.

Related Question