7
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ 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.) $\endgroup$ – david May 14 '13 at 23:54
  • 1
    $\begingroup$ See also cs.stackexchange.com/questions/10949/… $\endgroup$ – András Salamon May 15 '13 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.