{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:45:21Z","timestamp":1760244321376,"version":"build-2065373602"},"reference-count":39,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2022,11,28]],"date-time":"2022-11-28T00:00:00Z","timestamp":1669593600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Swedish Research Council","award":["621-2017-03750"],"award-info":[{"award-number":["621-2017-03750"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We introduce the concept of a k-dimensional matrix product D of k matrices A1,\u2026,Ak of sizes n1\u00d7n,\u2026,nk\u00d7n, respectively, where D[i1,\u2026,ik] is equal to \u2211\u2113=1nA1[i1,\u2113]\u00d7\u2026\u00d7Ak[ik,\u2113]. We provide upper bounds on the time complexity of computing the product and solving related problems of computing witnesses and maximum witnesses of the Boolean version of the product in terms of the time complexity of rectangular matrix multiplication. The multi-dimensional matrix product framework is useful in the design of parameterized graph algorithms. First, we apply our results on the multi-dimensional matrix product to the fundamental problem of detecting\/counting copies of a fixed pattern graph in a host graph. The recent progress on this problem has not included complete pattern graphs, i.e., cliques (and their complements, i.e., edge-free pattern graphs, in the induced setting). The fastest algorithms for the aforementioned patterns are based on a reduction to triangle detection\/counting. We provide an alternative simple method of detection\/counting copies of fixed size cliques based on the multi-dimensional matrix product. It is at least as time efficient as the triangle method in cases of K4 and K5. Next, we show an immediate reduction of the k-dominating set problem to the multi-dimensional matrix product. It implies the W[2] hardness of the problem of computing the k-dimensional Boolean matrix product. Finally, we provide an efficient reduction of the problem of finding the lowest common ancestors for all k-tuples of vertices in a directed acyclic graph to the problem of finding witnesses of the Boolean variant of the multi-dimensional matrix product. Although the time complexities of the algorithms resulting from the aforementioned reductions solely match those of the known algorithms, the advantage of our algorithms is simplicity. Our algorithms also demonstrate the versatility of the multi-dimensional matrix product framework.<\/jats:p>","DOI":"10.3390\/a15120448","type":"journal-article","created":{"date-parts":[[2022,11,28]],"date-time":"2022-11-28T09:09:42Z","timestamp":1669626582000},"page":"448","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Multi-Dimensional Matrix Product\u2014A Natural Tool for Parameterized Graph Algorithms"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1805-5654","authenticated-orcid":false,"given":"Miros\u0142aw","family":"Kowaluk","sequence":"first","affiliation":[{"name":"Institute of Informatics, University of Warsaw, 00-927 Warsaw, Poland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4998-9844","authenticated-orcid":false,"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Lund University, Box 118, 22100 Lund, Sweden"}]}],"member":"1968","published-online":{"date-parts":[[2022,11,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0304-3975(75)90009-2","article-title":"Complexity of Monotone Networks for Boolean Matrix Product","volume":"1","author":"Paterson","year":"1975","journal-title":"Theor. Comput. Sci."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0304-3975(76)90083-9","article-title":"A Lower Bound on the Number of Additions in Monotone Computations","volume":"2","author":"Schnorr","year":"1976","journal-title":"Theor. Comput. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/BF02165411","article-title":"Gaussian elimination is not optimal","volume":"13","author":"Strassen","year":"1969","journal-title":"Numer. Math."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Alman, J., and Williams, V.V. (2021, January 10\u201313). A Refined Laser Method and Faster Matrix Multiplication. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), Virtual.","DOI":"10.1137\/1.9781611976465.32"},{"key":"ref_5","unstructured":"Aumman, N., Levenstein, M., Levenstein, N., and Tsur, D. (2007, January 9\u201311). Finding witnesses by peeling. Proceedings of the Combinatorial Pattern Matching (CPM), London, ON, Canada."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Muthukrshnan, S. (1995, January 5\u20137). New results and open problems related to non-standard stringology. Proceedings of the 6th Combinatorial Pattern Matching (CPM), Espoo, Finland.","DOI":"10.1007\/3-540-60044-2_50"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Alon, N., Galil, Z., Margalit, O., and Naor, M. (1992, January 24\u201327). Witnesses for Boolean matrix multiplication and for shortest paths. Proceedings of the 33rd Symposium on Foundations of Computer Science (FOCS), Pittsburgh, PA, USA.","DOI":"10.1109\/SFCS.1992.267748"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1145\/567112.567114","article-title":"All pairs shortest paths using bridging sets and rectangular matrix multiplication","volume":"49","author":"Zwick","year":"2002","journal-title":"J. ACM"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.tcs.2007.02.053","article-title":"Faster algorithms for finding lowest common ancestors in directed acyclic graphs","volume":"380","author":"Czumaj","year":"2007","journal-title":"Theor. Comput. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1007\/s00453-009-9328-x","article-title":"All-Pairs Bottleneck Paths in Vertex Weighted Graphs","volume":"59","author":"Shapira","year":"2011","journal-title":"Algorithmica"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1007\/BF01940874","article-title":"Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions","volume":"16","author":"Alon","year":"1996","journal-title":"Algorithmica"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1322","DOI":"10.1137\/140978211","article-title":"Detecting and Counting Small Pattern Graphs","volume":"29","author":"Floderus","year":"2015","journal-title":"SIAM J. Discret. Math."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Williams, V.V., Wang, J.R., Williams, R., and Yu, H. (2015, January 4\u20136). Finding Four-Node Subgraphs in Triangle Time. Proceedings of the SODA, San Diego, CA, USA.","DOI":"10.1137\/1.9781611973730.111"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1093\/bioinformatics\/btn163","article-title":"Biomolecular network motif counting and discovery by color coding","volume":"24","author":"Alon","year":"2008","journal-title":"Bioinformatics"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Schank, T., and Wagner, D. (2005). Finding, Counting and Listing All Triangles in Large Graphs, an Experimental Study. Experimental and Efficient Algorithms, WEA 2005, Springer.","DOI":"10.1007\/11427186_54"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1640457.1640458","article-title":"Automatic Design of Application-Specific Reconfigurable Processor Extensions with UPaK Synthesis Kernel","volume":"15","author":"Wolinski","year":"2009","journal-title":"ACM Trans. Des. Autom. Electron. Syst."},{"key":"ref_17","unstructured":"Sekar, V., Xie, Y., Maltz, D.A., Reiter, M.K., and Zhang, H. (2004, January 15\u201316). Toward a framework for internet forensic analysis. Proceedings of the Third Workshop on Hot Topics in Networking (HotNets-HI), San Diego, CA USA."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1137\/0207033","article-title":"Finding a minimum circuit in a graph","volume":"7","author":"Itai","year":"1978","journal-title":"SIAM J. Comput."},{"key":"ref_19","first-page":"415","article-title":"On the complexity of the subgraph problem","volume":"26","author":"Poljak","year":"1985","journal-title":"Comment. Math. Univ. Carol."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.tcs.2004.05.009","article-title":"On the complexity of fixed parameter clique and dominating set","volume":"326","author":"Eisenbrand","year":"2004","journal-title":"Theor. Comput. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/S0020-0190(00)00047-8","article-title":"Finding and counting small induced subgraphs efficiently","volume":"74","author":"Kloks","year":"2000","journal-title":"Inf. Process. Lett."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1137\/110859798","article-title":"Counting and detecting small subgraphs via equations and matrix multiplication","volume":"27","author":"Kowaluk","year":"2013","journal-title":"SIAM J. Discret. Math."},{"key":"ref_23","unstructured":"Bl\u00e4ser, M., Komarath, B., and Sreenivasaiah, K. (2018). Graph Pattern Polynomials. arXiv."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Dalirrooyfard, M., Vuong, T.D., and Williams, V.V. (2019, January 23\u201326). Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Phoenix, AZ, USA.","DOI":"10.1145\/3313276.3316329"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/j.tcs.2015.09.001","article-title":"Induced subgraph isomorphism: Are some patterns substantially easier than others?","volume":"605","author":"Floderus","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Patrascu, M., and Williams, R. (2010, January 17\u201319). On the Possibility of Faster SAT Algorithms. Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA 2010), Austin, TX, USA.","DOI":"10.1137\/1.9781611973075.86"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (1999). Parameterized Complexity, Springer.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Ducournau, R., and Habib, M. (1987, January 15\u201317). On some algorithms for multiple inheritance in object-oriented programming. Proceedings of the ECOOP\u2019 87 European Conference on Object-Oriented Programming, Paris, France.","DOI":"10.1007\/3-540-47891-4_23"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/j.ipl.2010.02.014","article-title":"New common ancestor problems in trees and directed acyclic graphs","volume":"110","author":"Fischer","year":"2010","journal-title":"Inf. Process. Lett."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1137\/0205011","article-title":"On finding lowest common ancestors in trees","volume":"5","author":"Aho","year":"1976","journal-title":"SIAM J. Comput."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Bender, M.A., and Farach-Colton, M. (2000, January 10\u201314). The LCA problem revisited. Proceedings of the 4th Latin American Symposium on Theoretical Informatics (LATIN\u201900), Punta del Este, Uruguay.","DOI":"10.1007\/10719839_9"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Eckhardt, S., M\u00fchling, A.M., and Nowak, J. (2007, January 8\u201310). Fast lowest common ancestor computations in dags. Proceedings of the 15th Annual European Symposium on Algorithms (ESA), Eilat, Israel.","DOI":"10.1007\/978-3-540-75520-3_62"},{"key":"ref_33","unstructured":"Grandoni, F., Italiano, G.F., Lukasiewicz, A., Parotsidis, N., and Uznanski, P. (2021, January 10\u201313). All-Pairs LCA in DAGs: Breaking through the O(n2.5) barrier. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), Virtual."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","article-title":"Fast algorithms for finding nearest common ancestors","volume":"13","author":"Harel","year":"1984","journal-title":"SIAM J. Comput."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.jalgor.2005.08.001","article-title":"Lowest common ancestors in trees and directed acyclic graphs","volume":"57","author":"Bender","year":"2005","journal-title":"J. Algorithms"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/j.tcs.2008.01.032","article-title":"All-Pairs Disjoint Paths from a Common Ancestor in 0\u02dc(n\u03c9) Time","volume":"396","author":"Yuster","year":"2008","journal-title":"Theor. Comput. Sci."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Kowaluk, M., Lingas, A., and Nowak, J. (2008, January 2\u20134). A Path Cover Technique for LCAs in Dags. Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT 2008), Gothenburg, Sweden.","DOI":"10.1007\/978-3-540-69903-3_21"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Le Gall, F., and Urrutia, F. (2018, January 7\u201310). Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor. Proceedings of the SODA, New Orleans, LA, USA.","DOI":"10.1137\/1.9781611975031.67"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","article-title":"Strong computational lower bounds via parameterized complexity","volume":"72","author":"Chen","year":"2006","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/12\/448\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:28:37Z","timestamp":1760146117000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/12\/448"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,28]]},"references-count":39,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2022,12]]}},"alternative-id":["a15120448"],"URL":"https:\/\/doi.org\/10.3390\/a15120448","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,11,28]]}}}