Witnesses for Boolean matrix multiplication and for transitive closure (Q1260654)

The authors consider the Boolean matrix multiplication: \(C = A\cdot B\), \(C_{ij} = \bigvee^ n_{k=1}(A_{ik}\wedge B_{kj})\). An index \(k\) such that \(A_{ik}=B_{kj} = 1\) is called a witness (for the fact that \(C_{ij} = 1)\). A deterministic algorithm is proposed for computing the matrix of witnesses in time \(O(n^{\omega+\varepsilon})\), for \(\omega \leq 3\), \(\varepsilon > 0\). The problem of witnesses for Boolean matrix multiplication is related to the shortest paths problem. Also, an algorithm is proposed for computing witnesses for the transitive closure which has the same time complexity as the time needed to compute witnesses for Boolean matrix multiplication.