All Pairs Shortest Path - Directed graph with integer weights

Question

I don't understand how Distance Product works (or Min Plus Product). If we replace each argument in $A$ from $a_{i,j}$ to $x^{a_{i,j}}$ and each argument in $B$ from $b_{i,j}$ to $x^{b_{i,j}}$ and each and make the polinomial product on each row and column we'll get a matrix $C$ such $c_{i,j}= \sum_{\substack{1<k<n \\}} cx^{a_{i,k}+b_{k,j}})$.

1. We want the path, not only the distance, and for the path we must know $k$ which gives us the minimum $x^{a_{i,k}+b_{k,j}}$. So how do we extract k from it?
2. Why does the time of Distance Product is $O(n^{\omega}M)$? (where $\omega$ is the present lowest exponent for matrix multiplication and $M$ is the maximum value in the matrices).

Answer 1

I'll first answer question (2). Let's solve the $(\max,+)$ product problem. The $(\min,+)$ product can be solved analogously by negating entries and adding $M$ to each entry to make all entries positive.

Take $A$ and $B$ whose product $C$ we want to compute, and create matrices $A'$ and $B'$ where $A'[i,j]=(n+1)^{A[i,j]}$ and $B'[i,j]=(n+1)^{B[i,j]}$ for all $i,j$. Compute the product $C'$ of $A'$ with $B'$. This takes $O(Mn^\omega \log n)$ time since the bit representation of the integers in $A'$ and $B'$ has length $O(M\log n)$. Consider now $C'[i,j]=\sum_k A'[i,k]B'[k,j]=\sum_k (n+1)^{A[i,k]+B[k,j]}$. If $\max_k A[i,k]+B[k,j] = z$, then $C'[i,j]\geq (n+1)^z$, and if $\max_k A[i,k]+B[k,j]<z$, then $C'[i,j]\leq n\cdot (n+1)^{z-1} < (n+1)^z$. Thus, $C[i,j]$ is the largest power of $n+1$ that's at most $C'[i,j]$ and hence $C$ is easy to obtain from $C'$.

With respect to question (1), in order to find for each $i,j$, the index $k$ that achieves the minimum (called the witness), one uses a method by Zwick (from Uri Zwick. 2002. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49, 3 (May 2002), 289-317.) This method is based on ideas from an earlier paper by Alon, Galil, Margalit and Naor on finding witnesses for Boolean matrix multiplication.

The basic idea is to first figure out a way to extract the witness $k$ for entry $i,j$ provided $k$ is a unique witness for the minimum. Then one uses a carefully chosen, polylogarithmic number of random samples of columns of $A$/rows of $B$ which ensures that $k$ is the unique witness for $i,j$ in one of the samples with high probability. To extract a unique witness, one only needs to do $\log n$ distance products. For each $l=1,\ldots,\log n$, let $K_l$ be the integers whose $l$th bit is $1$, and compute the distance product of $A$ and $B$, restricted to the columns of $A$/rows of $B$ with indices in $K_l$. Then if $k$ is unique such that $C[i,j]=A[i,k]+B[k,j]$, one can compute the the binary representation of $k$ by setting to $1$ only those bits $l$ for which the distance product for $K_l$ had $C[i,j]$ as its $i,j$ entry.