Having number of walks between two vertices how to calculate paths

Question

I know that we can calculate number of walks with n length between two vertices of an undirected graph by calculating the nth power of the adjancy matrix but what if you want to avoid repetition in edges and vertices can you still use the nth power of the adjancy matrix and divise it by sth or perform some operation to remove the repetition? Any help is appreciated

Answer 1

I would like to formalize your question first.

Let $G=(V,E)$ be an undirected graph with $n$ vertices and $m$ edges. Without the loss of generality we can assume that $G$ is connected (because if $G$ is not connected, we could simply apply our algorithm to all components of $G$ and sum up the results).

Def. 1: A walk of length $k$ is a sequence of vertices $v_0,\cdots,v_k \in V$ such that $v_i$ and $v_{i+1}$ are connected by an edge of $E$, for any $0 \leq i < k$.

Def. 2: A path $P$ of length $k$ is a walk $v_0,\cdots,v_k$ such that any two vertices $v_i$ and $v_j$ are distinct, for $0 \leq i < j \leq k$. We call a path from vertex $v_i$ to vertex $v_j$ a $v_iv_j$-path.

Let us call a path from a vertex $v_i$ to a vertex $v_j$ simply $v_iv_j$ and denote its length $|v_iv_j|$.

Let us denote the set of $v_iv_j$-paths in a graph $G$ by $\mathcal{P}_G(v_iv_j)$ for any given $v_i,v_j \in V$.

Problem Instance: Two vertices $v_i,v_j$ of a graph $G=(V,E)$ and an integer $k$.

Question: What is the cardinality of $\mathcal{P}_G(v_iv_j)$ for $|v_iv_j|=k$?

First notice that this cannot be done in general using the adjacency matrix of $G$ alone, at least as far as I am concerned. Actually, I don't know of any nor have I found a method that generally solve this problem efficiently. What is generally known is that this problem is hard, in fact it is $\#P$-complete.

I think that you could generate all possible solutions using the Depth-First-Search (DFS) and then backtracking for listing all possible paths, then filter for your desired length. Keep in mind that this has a running time complexity of $O(n!)$ for $n$ being the number of vertices, which is insane. The algorithm is described here.

However, there are a few papers that I would like to propose. If your paths are short, there exists a general enumeration formula. Take a look at

• "On the number of paths of lengths 3 and 4 in a graph" by Movarraei and Shikare,
• "On the number of paths of length 5 in a graph" by Movarraei and Boxwala.

both in the International Journal of Applied Mathematical Research.

Not answering your question directly, but still closely related are the following paper.

• "A General Purpose Algorithm for Counting Simple Cycles and Simple Paths of Any Length" by Giscard et. al, Springer,
• "Optimal Listing of Cycles and st-Paths in Undirected Graphs" by Birmelé et. al in Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms.

This is not new, in fact there is a publication from 1966 by Ponstein called "Self-avoiding paths and the adjcency matrix of a graph".

There is a method for counting the number of $v_iv_j$-paths using a stochastical approach. It is called

• "Estimating the Number of s-t Paths in a Graph" by Roberts and Kroese in Journal of Graph Algorithms and Applications.