3
$\begingroup$

I am aware of the method for calculating the number of paths between each node in a graph G using the adjacency matrix of G.

Let $A$ be the adjacency matrix of G, then we can calculate the number of paths between each pair of nodes of length n, by raising $A$ to the $n$-th power. i.e $a^n_{i,j}$ (the $(i,j)$-th entry of $A^n$) gives the number of paths from node $i$ to node $j$ that takes $n$ steps.

Is there some similar method we can use to subtract away the paths that go through the same node twice?

$\endgroup$
2
  • $\begingroup$ Upon further reading paths with non-repeating nodes are called simple paths. If they start and end on the same node, with no other repeating nodes they are called simple cycles. If the path visits every node then it's called a hamiltonian path, if it visits all and ends on a node adjacent to the starting node it's called a hamiltonian cycle. $\endgroup$ Aug 10, 2022 at 15:51
  • 1
    $\begingroup$ The best new.technique for this sort of counting problem is binary decision diagrams. Try this 1994 paper, which counts for the first time the number of hamiltonian cycles of a certain graph with 64 vertices and several hundred edges: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8394 $\endgroup$
    – MJD
    Aug 11, 2022 at 10:57

2 Answers 2

3
$\begingroup$

No, there cannot be an equally simple method such as taking the powers of the adjacency matrix. Imagine that there were a polynomial method to count the number of simple paths from $v$ to $w$ of length $k$ in $G$. Then by applying this method on each adjacent pair $\{v,w\}$ with paths of length $|V|$, we would know if $G$ contains a Hamiltonian cycle.

So unless P=NP, even knowing if there is at least one simple path from $v$ to $w$ with length $k$, will require hard (=non-polynomial) computations, let alone counting them all. This could also be seen from the fact that finding the longest simple path in a graph is also a known NP-hard problem.

$\endgroup$
2
  • $\begingroup$ the algo defined in the last section of yaroslavvb.com/papers/ponstein-self.pdf is pretty simple - what it's complexity be? $\endgroup$ Aug 10, 2022 at 7:06
  • 1
    $\begingroup$ The linked algorithm is just a hard way to say: save all intermediary simple paths in a 'matrix'. The problem is: there can be an exponential number of simple paths of length k, so doing the multiplication can take an exponential amount of time. I don't think this 'algorithm' was made with computers in mind, for it would be quite hard to implement. $\endgroup$
    – Steven
    Aug 14, 2022 at 18:24
0
$\begingroup$

The last section "An algorithm for finding all simple paths and all simple cycles" of Self-Avoiding Paths and the Adjacency Matrix of a Graph gives something close to the posted question. It's similar to the usual $A^n$ trick in that it requires repeated multiplication of $A$ ($A-diag(A)$ if there are nodes connected to themselves), with the additional steps of setting diagonal entries of the intermediate matrices to 0, and an additional check (see step 7 below).

It's quite a bit different than the usual method, as each entry in A is given by a variable representing the edge weight instead of some numeric value. If G is the following graph: enter image description here.

Then the corresponding adjacency matrix A is given by:

\begin{bmatrix} 0 & x_{1} & 0 & 0 \\ x_{2} & 0 & x_{3} & 0 \\ x_{4} & 0 & 0 & x_{5} \\ x_{6} & 0 & x_{7} & x_{8} \\ \end{bmatrix}

Multiplication of variables corresponds to concatenation, addition corresponds to the seperation of different path instances. For example, $(x_1x_2)(x_3+x_4) = x_1x_2x_3 + x_1x_2x_4$. Note that you cannot replace the variables with their actual value (until the algorithm is finished) as order will be lost and the actual paths in each cell will be replaced by a single number. Once the algorithm is complete replacing each $x$ with 1, the $(i,j)$ entry of $C_k$ corresponds to the number of simple paths from $i$ to $j$ of length k.

ALGORITHM. Let k be given, where $k \geq 1$. Then the following algorithm yields all simple paths all simple cycles of length q for $q = 1, ... , k$.

  1. Let $D_1 = (A)_{i,i}=diag(A)$. Let $C_1 = A - D_1$. i.e. $D$ is the diagonal of $A$, and $C$ is the off diagonal entries of A.
  2. Let $q=1$
  3. Is $q = k$?
  4. If yes, $(C_t)_{i,j}$ represents all simple paths of length starting from the ith node and ending at the jth node. $D_t$ represents all simple cycles of length t starting from and ending at the ith node, t = 1, ...,k and the algorithm is finished.
  5. If no, calculate $C_1C_q$, and $C_qC_1$.
  6. Let $D_{q+1} = diag(C_qC_1) = diag(C_1C_q)$
  7. Define the matrix $C_{q+1}$ by $(C_{q+1})_{i,i} = 0$ and for $i \neq j$, $(C_{q+1})_{i,j}$ equal to the terms that occur in both $(C_1C_q)_{i,j}$, and $(C_qC_1)_{i,j}$
  8. Let q=q+1
  9. Go back to step 4

Step 7 needs a bit of explanation. I didn't quite get as it is phrased a bit confusingly in the paper. From construction we know $C_q$ has no repeated nodes, however $C_1C_q$ may in any given entry. If it does it will not appear in $C_qC_1$, hence the check. See the paper for a full proof by induction.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .