<p>So I had to answer the following question:</p>

<p>Given a graph $G = (V, E)$, and two vertices $v_i, v_j$, compute the number of walks between $v_i$ and $v_j$ of length <em>at most</em> $k$. $G$ is not too large, but $k$ is. In fact, we may even be interested in calculating this number modulo $n \in \mathbb{N}$.</p>

<p>If the question had been "of length <em>exactly</em> $k$", then the well known way is to take $A$ the adjacency matrix of $G$, and compute $A^k_{i, j}$. Since this can be done using exponentiation by squaring, we get $O(n^\omega \log n)$, where $\omega$ is the exponent of matrix multiplication.</p>

<p>In this case, the number I'm after is $\displaystyle \left(\sum_{r = 1}^k A^r\right)_{i, j}$. If these were numbers, or we knew that $A - I$ was invertible, we could compute the equivalent expression $\displaystyle \frac{A^{k + 1} - I}{A - I}$. In general, however, we do not know this, and we cannot invert $A - I$.</p>

<p>With that introduction, the idea of the algorithm is as follows:</p>

<p>Using the fact that $A^1 + A^2 + ... + A^k = T + A^{\lfloor\frac{k}{2}\rfloor} \cdot T$, where $T = A^1 + A^2 + ... + A^{\lfloor\frac{k}{2}\rfloor}$, plus $A^k$ if $k$ is odd. To avoid exponentiation $A$ each time, we maintain the invariant that after calling $F(t)$, $A$ is now $A^t$. Since we make at most three multiplications, and decrease $k$ by half each time, we again make $O(n^\omega\log n)$ operations. If we are interested in this number modulo $n$, even better, since these multiplications can all be done modulo $n$.</p>

<p>Code:</p>

<pre><code>A a global matrix, mutable input.
T a global matrix, output.
F(k):
  If k == 0:
    T := I.
    Return.
  If k == 1:
    T := A.
    Return.
  k' := floor(k / 2).
  F(k').
  T := T + A * T.
  A := A * A.
  If k == 1 (mod 2):
    A := A * A'.
    T := T + A.

A' := A.
F(k).
</code></pre>

<p>I feel this is a ridiculously simple algorithm, but I've failed to find any references to it. Does this technique have a name? I'm almost certain it must be well known!</p>

CC BY-SA 3.0
2013-05-14T23:54:32.050Z
It is indeed well known, but I don't think there is a name for it, other than it being an application of the 'divide and conquer' paradigm. In fact I have seen problems in programming contests where this technique provides the intended solution.
On the other hand, probably your problem can be reduced to the case where we need paths of length exactly $k$ by adding self loops from every vertex to itself. (This may require adding an additional copy of the vertices to avoid overcounting.)
david
CC BY-SA 3.0
2013-05-15T09:03:33.047Z
See also http://cs.stackexchange.com/questions/10949/all-paths-of-less-than-a-given-length-in-a-directed-graph-between-couple-of-node
András Salamon
<ds.algorithms><reference-request><graph-theory><linear-algebra><matrices>
An algorithm to compute the number of paths of length at most k
Federico Lebrón
# An algorithm to compute the number of paths of length at most k

(Asked by: username_0 on 2013-05-14)

So I had to answer the following question:
Given a graph $G = (V, E)$, and two vertices $v_i, v_j$, compute the number of walks between $v_i$ and $v_j$ of length at most $k$. $G$ is not too large, but $k$ is. In fact, we may even be interested in calculating this number modulo $n \in \mathbb{N}$.
If the question had been "of length exactly $k$", then the well known way is to take $A$ the adjacency matrix of $G$, and compute $A^k_{i, j}$. Since this can be done using exponentiation by squaring, we get $O(n^\omega \log n)$, where $\omega$ is the exponent of matrix multiplication.
In this case, the number I'm after is $\displaystyle \left(\sum_{r = 1}^k A^r\right)_{i, j}$. If these were numbers, or we knew that $A - I$ was invertible, we could compute the equivalent expression $\displaystyle \frac{A^{k + 1} - I}{A - I}$. In general, however, we do not know this, and we cannot invert $A - I$.
With that introduction, the idea of the algorithm is as follows:
Using the fact that $A^1 + A^2 + ... + A^k = T + A^{\lfloor\frac{k}{2}\rfloor} \cdot T$, where $T = A^1 + A^2 + ... + A^{\lfloor\frac{k}{2}\rfloor}$, plus $A^k$ if $k$ is odd. To avoid exponentiation $A$ each time, we maintain the invariant that after calling $F(t)$, $A$ is now $A^t$. Since we make at most three multiplications, and decrease $k$ by half each time, we again make $O(n^\omega\log n)$ operations. If we are interested in this number modulo $n$, even better, since these multiplications can all be done modulo $n$.
Code:
A a global matrix, mutable input.
T a global matrix, output.
F(k):
  If k == 0:
    T := I.
    Return.
  If k == 1:
    T := A.
    Return.
  k' := floor(k / 2).
  F(k').
  T := T + A * T.
  A := A * A.
  If k == 1 (mod 2):
    A := A * A'.
    T := T + A.

A' := A.
F(k).

I feel this is a ridiculously simple algorithm, but I've failed to find any references to it. Does this technique have a name? I'm almost certain it must be well known!

**Tags:** ds.algorithms, reference-request, graph-theory, linear-algebra, matrices
> **Comments:**
> **username_1**: It is indeed well known, but I don't think there is a name for it, other than it being an application of the 'divide and conquer' paradigm. In fact I have seen problems in programming contests where this technique provides the intended solution. On the other hand, probably your problem can be reduced to the case where we need paths of length exactly $k$ by adding self loops from every vertex to itself. (This may require adding an additional copy of the vertices to avoid overcounting.)  
> **username_2**: See also http://cs.stackexchange.com/questions/10949/all-paths-of-less-than-a-given-length-in-a-directed-graph-between-couple-of-node  

---

## 0 answers

