Arslan showed that computing all-pairs Hamming distances is easily reducible to arithmetic 0–1 matrix multiplication (IPL 2018). We provide a reverse, linear-time reduction of arithmetic 0–1 matrix multiplication to computing all-pairs distances in a Hamming space. On the other hand, we present a fast randomized algorithm for approximate all-pairs distances in a Hamming space. By combining it with our reduction, we obtain also a fast randomized algorithm for approximate 0–1 matrix multiplication. Finally, we present an output-sensitive randomized algorithm for a minimum spanning tree of a set of points in a generalized Hamming space, the lower is the cost of the minimum spanning tree the faster is our algorithm.(A preliminary version of this article appeared in arXiv.org.)

We study the design of efficient approximation algorithms for the ℓ-center clustering and minimum-diameter ℓ-clustering problems in high-dimensional Euclidean and Hamming spaces. Our main tool is randomized dimension reduction. First, we present a general method of reducing the dependency of the running time of a hypothetical algorithm for the ℓ-center problem in a high-dimensional Euclidean space on the dimension. Utilizing this method in part, we provide (2+ϵ)-approximation algorithms for the ℓ-center clustering and minimum-diameter ℓ-clustering problems in Euclidean and Hamming spaces that are substantially faster than the known 2-approximation algorithms when both ℓ and the dimension are super-logarithmic. Next, we apply the general method to the recent fast approximation algorithms with higher approximation guarantees for the ℓ-center clustering problem in a high-dimensional Euclidean space. Finally, we provide a speed-up of the known O(1)-approximation method for the generalization of the ℓ-center clustering problem that allows z outliers (i.e., z input points may be ignored when computing the maximum distance from an input point to a center) in high-dimensional Euclidean and Hamming spaces.

First, we present a new algorithm for the single-source shortest paths problem (SSSP) in edge-weighted directed graphs, with n vertices, m edges, and both positive and negative real edge weights. For a positive integer parameter t, in O(tm) time the algorithm finds for each vertex v a path distance from the source to v not exceeding that given by the shortest path from the source to v among the so called t+light paths. A directed path between two vertices is t+light if it contains at most t more edges than the minimum edge-cardinality directed path between these vertices. For t=O(n), our algorithm yields an O(nm)-time solution to SSSP in directed graphs with real edge weights matching the time complexity of the Bellman-Ford algorithm. Our next contribution is a new algorithm for the all-pairs shortest paths problem (APSP) in directed acyclic graphs (DAGs) with positive and negative real edge weights. The running time of the algorithm depends on such parameters as the number of leaves in (lexicographically first) shortest-paths trees, and the in-degrees in the input DAG. If the number of leaves is sufficiently small on the average, the algorithm is substantially faster than the best known algorithm in case of non-sparse DAGs. We also discuss an extension of hypothetical improved upper time-bounds for APSP in non-negatively edge-weighted DAGs to include directed graphs with a polynomial number of large directed cycles.

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.

We study applications of clustering (in particular the k-center clustering problem) in the design of efficient and practical deterministic algorithms for computing an approximate and the exact arithmetic matrix product of two 0-1 rectangular matrices A and B with clustered rows or columns, respectively. Let λA and λB denote the minimum maximum radius of a cluster in an ℓ-center clustering of the rows of A and in a k-center clustering of the columns of B,  respectively. In particular, when A and B are square matrices of size n×n, we obtain the following results. A simple deterministic algorithm that approximates each entry of the arithmetic matrix product of A and B within an additive error of at most 2λA in O(n2ℓ) time or at most 2λB in O(n2k) time.A simple deterministic preprocessing of the matrices A and B in O(n2ℓ) time or O(n2k) time after which every query asking for the exact value of an arbitrary entry of the arithmetic matrix product of A and B can be answered in O(λA) time or O(λB) time, respectively.A simple deterministic algorithm for the exact arithmetic matrix product of A and B running in time O(n2(ℓ+k+min{λA,λB})). A simple deterministic algorithm that approximates each entry of the arithmetic matrix product of A and B within an additive error of at most 2λA in O(n2ℓ) time or at most 2λB in O(n2k) time. A simple deterministic preprocessing of the matrices A and B in O(n2ℓ) time or O(n2k) time after which every query asking for the exact value of an arbitrary entry of the arithmetic matrix product of A and B can be answered in O(λA) time or O(λB) time, respectively. A simple deterministic algorithm for the exact arithmetic matrix product of A and B running in time O(n2(ℓ+k+min{λA,λB})).

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. 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 vectors are non-decreasing or both of them are non-increasing is as hard as the general case.

First, we present a new algorithm for the single-source shortest paths problem (SSSP) in edge-weighted directed graphs, with n vertices, m edges, and both positive and negative real edge weights. Given a positive integer parameter t, in O(tm) time the algorithm finds for each vertex v a path distance from the source to v not exceeding that yielded by the shortest path from the source to v among the so called t+ light paths. A directed path between two vertices is t+ light if it contains at most t more edges than the minimum edge-cardinality directed path between these vertices. For t= O(n), our algorithm yields an O(nm)-time solution to SSSP in directed graphs with real edge weights matching that of Bellman and Ford. Our main contribution is a new, output-sensitive algorithm for the all-pairs shortest paths problem (APSP) in directed acyclic graphs (DAGs) with positive and negative real edge weights. The running time of the algorithm depends on such parameters as the number of leaves in (lexicographically first) shortest-paths trees, and the in-degrees in the input graph. If the trees are sufficiently thin on the average, the algorithm is substantially faster than the best known algorithm. Finally, we discuss an extension of hypothetical improved upper time-bounds for APSP in non-negatively edge-weighted DAGs to include directed graphs with a polynomial number of large directed cycles.

Henzinger et al. posed the so-called Online Boolean Matrix-vector Multiplication (OMv) conjecture and showed that it implies tight hardness results for several basic dynamic or partially dynamic problems [STOC'15]. We first show that the OMv conjecture is implied by a simple off-line conjecture that we call the MvP conjecture. We then show that if the definition of the OMv conjecture is generalized to allow individual (i.e., it might be different for different matrices) polynomial-time preprocessing of the input matrix, then we obtain another conjecture (called the OMvP conjecture) that is in fact equivalent to our MvP conjecture. On the other hand, we demonstrate that the OMv conjecture does not hold in restricted cases where the rows of the matrix or the input vectors are clustered, and develop new efficient randomized algorithms for such cases. Finally, we present applications of our algorithms to answering graph queries. (c) 2021 Elsevier Inc. All rights reserved.

We study the problem of determining the Boolean product of two n x n Boolean matrices in an unconventional computational model allowing for mechanical operations. We show that O(n(2)) operations are sufficient to compute the product in this model.

We study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H = (V-H, A(H)) of D such that (a) S subset of V-H, (b) H is the union of k directed walks in D, and (c) the underlying graph of H includes a Steiner tree for S in D. Since a directed walk is a not necessarily a simple directed path, the problem is actually on covering with paths. We provide several results on the polynomial time tractability, hardness, and parameterized complexity of the problem. Our main fixed-parameter algorithm is randomized. (C) 2018 Elsevier Inc. All rights reserved.