Fast practical algorithms for the Boolean-product-witness-matrix problem

Abstract

Given two n×n Boolean matrices A and B, their Boolean Product Witness Matrix (BPWM) is an n×n integer matrix W with wij = some k such that aik = bkj = 1, (1≤i, j, k≤n) and wij = 0 if no such k exists. The best known algorithms to date for solving the BPWM problem have a worst-case complexity of O(n$+ω/ log n), where O(n$+ω/) is the time required to multiply two n×n integer matrices. The theoretically best known value of ω is 2.376, but is higher for algorithms that are practical to implement for reasonable problem sizes. In this paper, we present a relatively simple and practical randomized algorithm for solving the BPWM problem. The expected completion time of our algorithms is O(n2 log n) for a large class of Boolean matrices, including but not limited to all mutually-independent matrices. We show that the probability of the algorithm requiring more than O(n2 log n) is vanishingly small for most input Boolean matrices, irrespective of the density of 1's or 0's in them.