Abstract
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
where ω<2.376 is the matrix multiplication exponent, or, if fast rectangular matrix multiplication is used, in time
In particular, if ω−1<α<2 where m=n α, the new algorithm is faster than both of the aforementioned algorithms.
Similar content being viewed by others
Notes
We use the 2.376 bound in this paper in order to make it easy to compare with related results; one can easily plug in the value 2.373 whenever ω is used to obtain slightly improved exponents.
Computing maximum witnesses is computationally equivalent to computing minimum witnesses, so we only consider minimum witnesses.
Throughout this paper, \(\tilde{O}(f(n))\) stands for O(f(n)logc n) for some c>0.
Rounding issues are ignored in this paper as they have no effect on the asymptotic running times.
References
Alon, N., Naor, M.: Derandomization, witnesses for boolean matrix multiplication and construction of perfect hash functions. Algorithmica 16(4), 434–449 (1996)
Blelloch, G.E., Vassilevska, V., Williams, R.: A new combinatorial approach for sparse graph problems. In: Proceedings of the 35th International Colloquium on Automata, Languages and Programming, pp. 108–120. Springer, Berlin (2008)
Coppersmith, D.: Rectangular matrix multiplication revisited. J. Complex. 13(1), 42–49 (1997)
Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9(3), 251–280 (1990)
Czumaj, A., Kowaluk, M., Lingas, A.: Faster algorithms for finding lowest common ancestors in directed acyclic graphs. Theor. Comput. Sci. 380(1–2), 37–46 (2007)
Czumaj, A., Lingas, A.: Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication. SIAM J. Comput. 39(2), 431–444 (2009)
Galil, Z., Margalit, O.: Witnesses for boolean matrix multiplication and for transitive closure. J. Complex. 9(2), 201–221 (1993)
Huang, X., Pan, V.Y.: Fast rectangular matrix multiplication and applications. J. Complex. 14, 257–299 (1998)
Kowaluk, M., Lingas, A.: LCA queries in directed acyclic graphs. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, pp. 241–248. Springer, Berlin (2005)
Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci. 51(3), 400–403 (1995)
Shapira, A., Yuster, R., Zwick, U.: All-pairs bottleneck paths in vertex weighted graphs. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 978–985. Society for Industrial and Applied Mathematics, Philadelphia (2007)
Strassen, V.: Gaussian elimination is not optimal. Numer. Math. 13(4), 354–356 (1969)
Vassilevska, V., Williams, R., Yuster, R.: Finding heaviest h-subgraphs in real weighted graphs, with applications. ACM Trans. Algorithms 6(3), 1–23 (2010)
Vassilevska Williams, V.: Multiplying matrices faster than coppersmith-winograd. In: Proceedings of the 44th Symposium on Theory of Computing, pp. 887–898. ACM Press, New York (2012)
Zwick, U.: All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49(3), 289–317 (2002)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Cohen, K., Yuster, R. On Minimum Witnesses for Boolean Matrix Multiplication. Algorithmica 69, 431–442 (2014). https://doi.org/10.1007/s00453-012-9742-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-012-9742-3