2
$\begingroup$

I was reading something about the concept of walks in a graph b/w a start vertex and a terminating vertex in a graph and then suddenly a problem struck me, is there any algorithm or a method that can be used to enumerate all the distinct walks from a start vertex to a terminal vertex in a graph, if so can you all point me to some relevant links to study this problem and what are some applications of solving this problem?

$\endgroup$

migrated from cstheory.stackexchange.com Jun 8 '12 at 6:29

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 1
    $\begingroup$ Depth-first search from the start vertex to the terminal vertex. When you find the terminal vertex don't stop, keep going, until the algorithm terminates. $\endgroup$ – M. Alaggan Jun 5 '12 at 13:46
  • 1
    $\begingroup$ Nowadays, the definition of walk allows cycles in it. So if the graph is connected but not a tree, there must be INFINITE walks, and it's impossible to enumerate. $\endgroup$ – Yixin Cao Jun 5 '12 at 14:42
  • 1
    $\begingroup$ Actually, even the graph is a tree, you can go along an edge back and forth for any times, and thus the number of walks is still infinite. On the other hand, take $A$ as the adjacency matrix of the graph, the $(i,j)$-element in the $k$-th power of $A$ ($A^k_{i,j}$) is the number of length-$k$ walks from the vertex $i$ to the vertex $j$. $\endgroup$ – Yixin Cao Jun 5 '12 at 14:55
8
$\begingroup$

If the input graph is undirected:

  • If the source vertex $s$ and target vertex $t$ are in different components of the graph, then there are no walks from $s$ to $t$.

  • If $s$ and $t$ are in the same component, and that component has only one vertex (so in particular, $s=t$), then there is exactly one walk from $s$ to $t$, namely the unique walk that starts at $s$ and has length $0$.

  • Otherwise, there are infinitely many walks from $s$ to $t$.


If the input graph is directed:

Let $S$ be the subset of vertices reachable from $s$, and let $T$ be the set of vertices from which $t$ is reachable. Finally, let $H$ be the induced subgraph of the input graph $G$ with vertices $S\cap T$. Every walk in $G$ from $s$ to $t$ is actually a walk in the subgraph $H$.

  • If $H$ is empty, there are no walks from $s$ to $t$.

  • If $H$ is a non-empty directed acyclic graph, then $s$ is the unique source, $t$ is the unique sink, and every walk from $s$ to $t$ is actually a simple path. The number of paths in a dag from a source to a sink can be computed in $O(m)$ time by dynamic programming. Remaining details are left as a homework exercise.

  • Otherwise, there are infinitely many walk from $s$ to $t$.

$\endgroup$
  • 2
    $\begingroup$ So the question is only interesting for directed graphs. What then? $\endgroup$ – Raphael Jun 8 '12 at 12:30
  • $\begingroup$ @JeffE: your comment applies since you are considering cycles. A natural constraint that can be added to the problem so that it becomes more interesting (I am referring to Raphael's comment here) is to forbid re-visiting nodes or to forbid traversing the same edge twice. $\endgroup$ – Carlos Linares López Nov 26 '12 at 22:32
  • $\begingroup$ @CarlosLinaresLópez: That should be a separate question! Counting paths or trails instead of walks is much more interesting/difficult. $\endgroup$ – JeffE Nov 26 '12 at 23:19
  • $\begingroup$ @JeffE: Agreed! All I wanted was just to remark that the problem might be interesting if additional constraints are imposed. Nevertheless, you are right and that should be a separate question $\endgroup$ – Carlos Linares López Nov 27 '12 at 10:07

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.