Witnesses for Boolean matrix multiplication and for shortest paths

Abstract

The subcubic (O(n/sup w/) for w(3) algorithms to multiply Boolean matrices do not provide the witnesses; namely, they compute C=A.B but if C/sub ij/=1 they do not find an index k (a witness) such that A/sub ik/=B/sub kj/=1. The authors design a deterministic algorithm for computing the matrix of witnesses that runs in O(n/sup w/) time, where here O(n/sup w/) denotes O(n/sup w/(log n)/sup O(1)/). The subcubic methods to compute the shortest distances between all pairs of vertices also do not provide for witnesses; namely they compute the shortest distances but do not generate information for computing quickly the paths themselves. A witness for a shortest path from v/sub i/ to v/sub j/ is an index k such that v/sub k/ is the first vertex on such a path. They describe subcubic methods to compute such witnesses for several versions of the all pairs shortest paths problem. As a result, they derive shortest paths algorithms that provide characterization of the shortest paths in addition to the shortest distances in the same time (up to a polylogarithmic factor) needed for computing the distances; namely O(n/sup (3+w)/2/) time in the directed case and O(n/sup w/) time in the undirected case. They also design an algorithm that computes witnesses for the transitive closure in the same time needed to compute witnesses for Boolean matrix multiplication.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>