0
$\begingroup$

Let's say I have a directed graph represented as an adjacency matrix, and I'm given two nodes $u,v$ and a parameter $k$. Let's also say that the maximal degree of a node in the graph is $d$.

What is the most efficient algorithm to find all paths of length $<=k$ from $u$ to $v$?

I know the number of such paths can be calculated efficiently using Dynamic Programming approach, but I'm looking for an algorithm that allows to get a set of actual paths.

It's clear that such algorithm would have a factor of the number of paths in its time complexity, which has $k$ in the exponent, but still, I would like to know what is the best approach for such a problem.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

I'm not sure whether "best" is answerable, but I will describe one simple strategy that appears reasonable. Let $S(u,v,d)$ be the set of all such paths of length $d$. Then

$$S(u,w,d+1) = \{u \leadsto v \to w \mid u \leadsto v \in S(u,v,d), v \to w \in E\}$$

Also $S(u,u,0) = \{u \to u\}$. This gives a dynamic programming algorithm for computing the set of all such paths, if you evaluate these sets in order of increasing $d$.

As an optimization, you can delete all vertices that aren't reachable from $u$ or that can't reach $v$ before beginning this computation. As another optimization, you can precompute the matrices $A^k$, where $A^k_{uv}=1$ if there is a path of length $k$ from $u$ to $v$ (these can be obtained from the adjacency matrix by repeated multiplication); then you only evaluate $S(u,w,d)$ for $u,w$ such that $A^d_{uw}=1$ and $A^{k-d}_{wv}=1$.

With these optimizations, if there are a total of $Q$ such paths that you want to output, then the running time will be at most $O(kQ \cdot |E|)$. There's not much opportunity to do much better than that; obviously any algorithm must take at least $\Omega(Q)$ time, and since $Q$ will typically be exponentially large compared to $k|E|$, the gap between the upper and lower bounds will typically be a small factor compared to the total running time.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, this is actually the solution I had in mind, but is it the most efficient? For implementing this with dynamic programming, one would require to go over al paths already stored in $S(u,w,k)$ in order to calculate $S(u,v,k+1)$, for every $w$ which is a neighbour of $v$, which will imply a very large exponential dependency... $\endgroup$
    – Ofir Gordon
    Jun 4, 2020 at 5:30
  • $\begingroup$ @OfirGordon, see revised answer for an analysis of the running time. The exponential dependency is inherent in the fact that there can be exponentially many paths, and you need to output all of them, so it takes exponential time even to output them all, let alone to find them in the first place. $\endgroup$
    – D.W. ♦
    Jun 4, 2020 at 6:49
  • $\begingroup$ Those are great optimization ideas, thanks. Regarding the complexity analysis, in the worst case, the part in the algorithm in which in order to calculate $S(u,w,d)$ it needs to iterate over all paths in $S(u,x,d-1)$ (for each neighbour $x$ of $w$), won't result in a factor $Q^\alpha$ in the xomplexity? (for some constant $\alpha$). I'm failling to understand why this part won't increase the complexity to be much greater then Ω(Q) $\endgroup$
    – Ofir Gordon
    Jun 4, 2020 at 16:58
  • $\begingroup$ @OfirGordon, nope, because you compute it once. The size of each $S(u,w,d)$ is at most $Q$; in fact, $\sum_{w} |S(u,w,d)| \le Q$. For each $d$, we do at most $|E| \cdot \sum_{w} |S(u,w,d)|$ work. $\endgroup$
    – D.W. ♦
    Jun 4, 2020 at 17:53

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.