On Minimum Witnesses for Boolean Matrix Multiplication
Minimum witnesses for Boolean matrix multiplication play an important role in several graph algorithms. For two Boolean matrices A and B of order n, with one of the matrices having at most m nonzero entries, the fastest known algorithms for computing the minimum witnesses of their product run in either O(n 2.575) time or in O(n 2+mnlog(n 2/m)/log2 n) time. We present a new algorithm for this problem. Our algorithm runs either in time $$\tilde{O}\bigl(n^{\frac{3}{4-\omega}}m^{1-\frac{1}{4-\omega }}\bigr) $$ where ?<2.376 is the matrix multiplication exponent, or, if fast rectangular matrix multiplication is used, in time $$O\bigl(n^{1.939}m^{0.318}\bigr). $$ In particular, if ??1<?<2 where m=n ? , the new algorithm is faster than both of the aforementioned algorithms.
minimum witness boolean matrix multiplication