5
$\begingroup$

Sorry for bad English.

Consider a graph $G$ with the adjacency matrix $A$. I know that the number of paths of the length $n$ is the sum of elements $A^n$.

But what if we can't walk through a vertex more than one times?

$\endgroup$
5
  • 5
    $\begingroup$ It that would be as simple as some modified $A^n$, then you would solve Hamiltonian path problem in polynomial time. Of course, we don't know whether $P = NP$ or not, but I strongly suspect, that your formula to be easily provable, will have to include (somewhere, maybe indirectly) exponential number of operations, e.g. $2^n$ additions, multiplications, assignments, whatever. $\endgroup$
    – dtldarek
    Feb 10, 2013 at 9:36
  • $\begingroup$ @dtldarek: Isn't $A^n$ exponential in $n$? $\endgroup$ Feb 10, 2013 at 9:52
  • $\begingroup$ @Raskolnikov In terms of number of operations, no. E.g. $a^{12} = a\cdot a \cdot a \cdot \ldots \cdot a$ which uses only linear number of multiplications. Moreover, if you rearrange it smartly (that is via Horner's scheme) you can make it even logarithimc in $n$, e.g. $a^{12} = ((a^2\cdot a)^2)^2$. $\endgroup$
    – dtldarek
    Feb 10, 2013 at 10:52
  • $\begingroup$ @dtldarek: Yes, but that only computes how many paths of length $n$ there are. Searching those paths for Hamiltonian ones means searching through an exponentially growing number of paths, regardless of how fast that number can be computed. $\endgroup$ Feb 10, 2013 at 11:59
  • $\begingroup$ @Raskolnikov An oracle that calculates the number of paths of length $|V|$ that doesn't go twice through any vertex is enough to solve Hamiltonian path problem. Moreover, even if the original problem is of the form "is there a Hamiltonian path of length $k$", it is easy to compute the path itself – just remove any unnecessary edges until a single path remains. $\endgroup$
    – dtldarek
    Feb 10, 2013 at 15:28

3 Answers 3

3
$\begingroup$

There doesn't seem to be a simple expression involving the adjacency matrix for the number of simple (i.e. self-avoiding) paths in an arbitrary graph, but there is an algorithm.

Googling "adjacency matrix number of paths" turned up this SE question which points out (with a nice example) that powers of the adjacency matrix count the number of walks of length $n$, not paths. That fact also turned up in this wikipedia entry. These walks allow a vertex to be visited more than once, so it's unlikely they can help you to count simple paths.

The paper Self-Avoiding Paths and the Adjacency Matrix of a Graph - J. Ponstein contains an algorithm on pages 9-10 which counts all simple paths in an arbitrary graph.

Edit: The good news is explicit formulae for the paths of length $n$ exist, the bad news is the number of terms in the formulae grow exponentially with $n$!

The paper On the determination of redundancies in sociometric chains - Ross, Ian C.; Harary, Frank counts the number of 'redundant paths' (i.e. non-simple paths, walks of length $n$ where a vertex is visited more than once).

The English language powerpoint slideshow of the Russian language paper "The number of fixed length cycles in an undirected graph. Explicit formulae in case of small lengths" by S. N. Perepechko & A. N. Voropaev contains formula for path lengths 2-5 using the Ross & Harary method. I reproduce, for your delectation or horror, 2 of the 17476 terms from the path length 10 formula ($\times$ is element-wise matrix multiplication, $\cdot$ is ordinary matrix multiplication): enter image description here

$\endgroup$
0
1
$\begingroup$

[This is a counter-example to wece's answer, posted only as an answer because it's too long for a comment.]

wece's method is only correct for $A_2$. Counterexample: Let $A=\left[\begin{array}{ccccc}0&1&0&0&0\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\0&0&0&1&0\end{array}\right]$ representing a chain of 5 vertices connected by 4 edges. $A_1=A-diag(A)=A$.

$A_2=A\otimes A_1 =\left[\begin{array}{ccccc}1&0&1&0&0\\0&2&0&1&0\\1&0&2&0&1\\0&1&0&2&0\\0&0&1&0&1\end{array}\right]$.

In $A_2$ we see all the paths of length 2, the diagonal representing forbidden paths of length 2 from each vertex back to itself, the off-diagonal entries representing the 8 paths of length 2 (path from $a \rightarrow b$ distinct from $b \rightarrow a$). Then

$A_3 = A \otimes A_2 = \left[\begin{array}{ccccc}0&1&0&0&0\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\0&0&0&1&0\end{array}\right]\left[\begin{array}{ccccc}0&0&1&0&0\\0&0&0&1&0\\1&0&0&0&1\\0&1&0&0&0\\0&0&1&0&0\end{array}\right] = \left[\begin{array}{ccccc}0&0&0&1&0\\1&0&1&0&1\\0&1&0&1&0\\1&0&1&0&1\\0&1&0&0&0\end{array}\right]$,

which according to wece's method represents 10 paths of length 3, when there should be 3 such paths.

$\endgroup$
0
$\begingroup$

Let $A\otimes B$ be defined as the product of matrices where you removed the diagonal i.e.: $$A\otimes B=(A-diag(A))\times(B-diag(B))$$ Let $A_1=A$ and $A_n=A\otimes A_{n-1}$.

The number of paths of the length n without going through a vertex more than one times is equal to the sum of elements of $A_n$.

$\endgroup$
1
  • $\begingroup$ See the counter-example in my answer. $\endgroup$
    – Frentos
    Jan 5, 2016 at 13:22

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.