(min,+) matrix and vector products for inputs decomposable into few monotone subsequences
(2025) In Theoretical Computer Science 1037.- Abstract
We study the time complexity of computing the (min,+) matrix product of two n×n integer matrices in terms of n and the number of monotone subsequences the rows of the first matrix and the columns of the second matrix can be decomposed into. In particular, we show that if each row of the first matrix can be decomposed into at most m1 monotone subsequences and each column of the second matrix can be decomposed into at most m2 monotone subsequences such that all the subsequences are non-decreasing or all of them are non-increasing then the (min,+) product of the matrices can be computed in O(m1m2n2.569) time. On the other hand, we observe that if all the rows of the first matrix are... (More)
We study the time complexity of computing the (min,+) matrix product of two n×n integer matrices in terms of n and the number of monotone subsequences the rows of the first matrix and the columns of the second matrix can be decomposed into. In particular, we show that if each row of the first matrix can be decomposed into at most m1 monotone subsequences and each column of the second matrix can be decomposed into at most m2 monotone subsequences such that all the subsequences are non-decreasing or all of them are non-increasing then the (min,+) product of the matrices can be computed in O(m1m2n2.569) time. On the other hand, we observe that if all the rows of the first matrix are non-decreasing and all columns of the second matrix are non-increasing or vice versa then this case is as hard as the general one. We also present six cases of the restrictions on the input integer matrices under which the problem of computing the (min,+) matrix product is equally hard as that of computing the minimum and maximum witnesses of Boolean matrix product. Similarly, we also study the time complexity of computing the (min,+) convolution of two n-dimensional integer vectors in terms of n and the number of monotone subsequences the two vectors can be decomposed into. We show that if the first vector can be decomposed into at most m1 monotone subsequences and the second vector can be decomposed into at most m2 subsequences such that all the subsequences of the first vector are non-decreasing and all the subsequences of the second vector are non-increasing or vice versa then their (min,+) convolution can be computed in O˜(m1m2n1.5) time. On the other, the case when both sequences of consecutive coordinates of the vectors are non-decreasing or both of them are non-increasing is as hard as the general case. Finally, we present six cases of the restrictions on the input integer vectors under which the problem of computing the (min,+) vector convolution is equally hard as that of computing the minimum and maximum witnesses of the Boolean vector convolution.
(Less)
- author
- Lingas, Andrzej LU and Persson, Mia LU
- organization
- publishing date
- 2025-05-11
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- (min,+) convolution, (min,+) matrix product, All-pairs shortest-paths problem (APSP), Monotone sequence, Time complexity
- in
- Theoretical Computer Science
- volume
- 1037
- article number
- 115158
- publisher
- Elsevier
- external identifiers
-
- scopus:105000034918
- ISSN
- 0304-3975
- DOI
- 10.1016/j.tcs.2025.115158
- language
- English
- LU publication?
- yes
- additional info
- Publisher Copyright: © 2025 The Authors
- id
- 472b6f33-deb3-4a0e-8559-f7cf806a47df
- date added to LUP
- 2026-06-11 11:13:46
- date last changed
- 2026-06-11 11:14:27
@article{472b6f33-deb3-4a0e-8559-f7cf806a47df,
abstract = {{<p>We study the time complexity of computing the (min,+) matrix product of two n×n integer matrices in terms of n and the number of monotone subsequences the rows of the first matrix and the columns of the second matrix can be decomposed into. In particular, we show that if each row of the first matrix can be decomposed into at most m<sub>1</sub> monotone subsequences and each column of the second matrix can be decomposed into at most m<sub>2</sub> monotone subsequences such that all the subsequences are non-decreasing or all of them are non-increasing then the (min,+) product of the matrices can be computed in O(m<sub>1</sub>m<sub>2</sub>n<sup>2.569</sup>) time. On the other hand, we observe that if all the rows of the first matrix are non-decreasing and all columns of the second matrix are non-increasing or vice versa then this case is as hard as the general one. We also present six cases of the restrictions on the input integer matrices under which the problem of computing the (min,+) matrix product is equally hard as that of computing the minimum and maximum witnesses of Boolean matrix product. Similarly, we also study the time complexity of computing the (min,+) convolution of two n-dimensional integer vectors in terms of n and the number of monotone subsequences the two vectors can be decomposed into. We show that if the first vector can be decomposed into at most m<sub>1</sub> monotone subsequences and the second vector can be decomposed into at most m<sub>2</sub> subsequences such that all the subsequences of the first vector are non-decreasing and all the subsequences of the second vector are non-increasing or vice versa then their (min,+) convolution can be computed in O˜(m<sub>1</sub>m<sub>2</sub>n<sup>1.5</sup>) time. On the other, the case when both sequences of consecutive coordinates of the vectors are non-decreasing or both of them are non-increasing is as hard as the general case. Finally, we present six cases of the restrictions on the input integer vectors under which the problem of computing the (min,+) vector convolution is equally hard as that of computing the minimum and maximum witnesses of the Boolean vector convolution.</p>}},
author = {{Lingas, Andrzej and Persson, Mia}},
issn = {{0304-3975}},
keywords = {{(min,+) convolution; (min,+) matrix product; All-pairs shortest-paths problem (APSP); Monotone sequence; Time complexity}},
language = {{eng}},
month = {{05}},
publisher = {{Elsevier}},
series = {{Theoretical Computer Science}},
title = {{(min,+) matrix and vector products for inputs decomposable into few monotone subsequences}},
url = {{http://dx.doi.org/10.1016/j.tcs.2025.115158}},
doi = {{10.1016/j.tcs.2025.115158}},
volume = {{1037}},
year = {{2025}},
}