A Multi-Dimensional Matrix Product—A Natural Tool for Parameterized Graph Algorithms
(2022) In Algorithms 15(12).- Abstract
We introduce the concept of a k-dimensional matrix product D of k matrices (Formula presented.) of sizes (Formula presented.) respectively, where (Formula presented.) is equal to (Formula presented.). 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... (More)
We introduce the concept of a k-dimensional matrix product D of k matrices (Formula presented.) of sizes (Formula presented.) respectively, where (Formula presented.) is equal to (Formula presented.). 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 (Formula presented.) and (Formula presented.). Next, we show an immediate reduction of the k-dominating set problem to the multi-dimensional matrix product. It implies the (Formula presented.) 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.
(Less)
- author
- Kowaluk, Mirosław and Lingas, Andrzej LU
- organization
- publishing date
- 2022-12
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- clique, lowest common ancestor, subgraph isomorphism, time complexity
- in
- Algorithms
- volume
- 15
- issue
- 12
- article number
- 448
- publisher
- MDPI AG
- external identifiers
-
- scopus:85144596639
- ISSN
- 1999-4893
- DOI
- 10.3390/a15120448
- language
- English
- LU publication?
- yes
- id
- 80cce3c8-1ece-489f-b2c0-eeb6602c3989
- date added to LUP
- 2023-01-09 12:17:59
- date last changed
- 2023-01-09 12:17:59
@article{80cce3c8-1ece-489f-b2c0-eeb6602c3989,
abstract = {{<p>We introduce the concept of a k-dimensional matrix product D of k matrices (Formula presented.) of sizes (Formula presented.) respectively, where (Formula presented.) is equal to (Formula presented.). 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 (Formula presented.) and (Formula presented.). Next, we show an immediate reduction of the k-dominating set problem to the multi-dimensional matrix product. It implies the (Formula presented.) 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.</p>}},
author = {{Kowaluk, Mirosław and Lingas, Andrzej}},
issn = {{1999-4893}},
keywords = {{clique; lowest common ancestor; subgraph isomorphism; time complexity}},
language = {{eng}},
number = {{12}},
publisher = {{MDPI AG}},
series = {{Algorithms}},
title = {{A Multi-Dimensional Matrix Product—A Natural Tool for Parameterized Graph Algorithms}},
url = {{http://dx.doi.org/10.3390/a15120448}},
doi = {{10.3390/a15120448}},
volume = {{15}},
year = {{2022}},
}