2
$\begingroup$

The problem is we have to count number of paths between a source and a destination in a graph. The brute force approach is using backtracking which is $O(n!)$.

Is there any better solution to this problem?

Note that we have to count paths so we can't visit the same node again in a path.

I think this problem is np-hard and is similar to finding hamiltonian path in a graph. So, I can use Held-Karp algorithm to solve it in $O(n^2*2^n)$ using dynamic programming. Am I right?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Note that there can be an exponential number of paths, so enumerating them certainly can't be done in polynomial time. $\endgroup$ – Draconis Jun 18 '18 at 1:01
  • $\begingroup$ But, I can use Held-Karp to reduce time complexity to $O(n^2*2^n)$ which is not polynomial but still better than $O(n!)$. Right?? $\endgroup$ – shiwang Jun 18 '18 at 11:25
4
$\begingroup$

Let $A$ denote the adjacency matrix, $A^k$ its $k$th power, and $(A^k)_{ij}$ the entry of $A^k$ at row $i$, column $j$. Then $(A^k)_{ij}$ is a count of the number of paths of length $k$ from node $i$ to node $j$.

Let $M = \text{Id} + A + A^2 + A^3 + \cdots$. Then $M_{st}$ is a count of the number of paths (of any length) from source $s$ to destination $t$. So, we just need to compute the matrix $M$. The matrix $M$ can be computed using the matrix identity

$$M = (\text{Id} - A)^{-1}.$$

Thus, with a matrix subtraction and inversion, then looking at the $u,j$ entry of the resulting inverse, you can obtain a count of the number of such paths.

This includes paths where a node can be repeated. If you want to count the number of simple paths, then the problem is #P-complete for general graphs (and thus likely has no efficient algorithm), or can be done in linear time for directed acyclic graphs by topological sorting and then using dynamic programming.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Firstly, how does this matrix identity come? And what if determinant of a matrix comes out to be zero. Secondly, assume a case there is a cycle present in the path between source and destination, then no of walks (if we are assuming any length) would keep on repeating, But according to your formula, no of walks of any length from a source to destination would comes to be constant. How does this makes sense? $\endgroup$ – shiwang Jun 19 '18 at 8:44
  • 1
    $\begingroup$ @shiwang $M = I + AM$ so $M(I-A) = I$ $\endgroup$ – Reinstate Monica Jun 19 '18 at 15:20
  • $\begingroup$ @shiwang, yes, you'll have to do some thinking about what happens if $\text{Id}-A$ is not invertible (I haven't thought about that carefully; I'm not even sure if it is possible or not). If there is a cycle reachable from $s$ and that can reach $t$, then the number of paths is infinite; that can be detected in linear time by decomposing into strongly connected components. $\endgroup$ – D.W.♦ Jun 19 '18 at 16:48
  • $\begingroup$ @D.W. If I directly calculate $M=Id+A+A2+A3+⋯ $ time complexity would be $O(n^3)$ (Note that outer loop will run for n times because it will cover all the walks with distance less than or equal to n and by running it one more time I can check whether there is a cycle between source and destination or not) .Finding inverse also takes $O(n^3)$ (and also we have to take care if the matrix is invertible or not). Don't you think finding it directly is better? $\endgroup$ – shiwang Jun 19 '18 at 18:16
  • $\begingroup$ @shiwang, I think the time complexity of summing the series directly would be $O(n^4)$, since you need to compute $\text{Id}+A+A^2 + \cdots + A^n$, which has $n$ terms, and computing $A^{i+1}$ from $A^i$ requires a matrix multiplication, which takes $O(n^3)$ time per term, for a total of $n \times O(n^3) = O(n^4)$ time. My algorithm, based on finding an inverse, takes only $O(n^3)$ time, which is faster. (I'm assuming you have checked first that there are no cycles, so you don't need to add in terms $A^i$ where $i>n$.) $\endgroup$ – D.W.♦ Jun 19 '18 at 20:14

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.