We say an algorithm on n × n matrices with integer entries in −M,M (or n-node graphs with edge weights from −M,M) is truly subcubic if it runs in O(n3 − δ poly(log M)) time for some δ > 0. We define ...a notion of subcubic reducibility and show that many important problems on graphs and matrices solvable in O(n3) time are equivalent under subcubic reductions. Namely, the following weighted problems either all have truly subcubic algorithms, or none of them do: *The all-pairs shortest paths problem on weighted digraphs (APSP). *Detecting if a weighted graph has a triangle of negative total edge weight. *Listing up to n2.99 negative triangles in an edge-weighted graph. *Finding a minimum weight cycle in a graph of non-negative edge weights. *The replacement paths problem on weighted digraphs. *Finding the second shortest simple path between two nodes in a weighted digraph. *Checking whether a given matrix defines a metric. *Verifying the correctness of a matrix product over the (min, +)-semiring. *Finding a maximum subarray in a given matrix. Therefore, if APSP cannot be solved in n3−ε time for any ε > 0, then many other problems also need essentially cubic time. In fact, we show generic equivalences between matrix products over a large class of algebraic structures used in optimization, verifying a matrix product over the same structure, and corresponding triangle detection problems over the structure. These equivalences simplify prior work on subcubic algorithms for all-pairs path problems, since it now suffices to give appropriate subcubic triangle detection algorithms. Other consequences of our work are new combinatorial approaches to Boolean matrix multiplication over the (OR,AND)-semiring (abbreviated as BMM). We show that practical advances in triangle detection would imply practical BMM algorithms, among other results. Building on our techniques, we give two improved BMM algorithms: a derandomization of the combinatorial BMM algorithm of Bansal and Williams (FOCS’09), and an improved quantum algorithm for BMM.
The All-pairs shortest path problem (ALL-SPP) aims to find the shortest path joining all the vertices in a given graph. This study proposed a new optimal method, Dhouib-matrix-ALL-SPP (DM-ALL-SPP) to ...solve the ALL-SPP based on column-row navigation through the adjacency matrix. DM-ALL-SPP is designed to generate in a single execution the shortest path with details among all-pairs of vertices for a graph with positive and negative weighted edges. Even for graphs with a negative cycle, DM-ALL-SPP reported a negative cycle. In addition, DM-ALL-SPP continues to work for directed, undirected and mixed graphs. Furthermore, it is characterized by two phases: the first phase consists of adding by column repeated (n) iterations (where n is the number of vertices), and the second phase resides in adding by row executed in the worst case (n∗log(n)) iterations. The first phase, focused on improving the elements of each column by adding their values to each row and modifying them with the smallest value. The second phase is emphasized by rows only for the elements modified in the first phase. Different instances from the literature were used to test the performance of the proposed DM-ALL-SPP method, which was developed using the Python programming language and the results were compared to those obtained by the Floyd-Warshall algorithm.
Display omitted
•A new optimal method (DM-ALL-SPP) is designed to find the shortest path between all vertices.•A stepwise application of DM-ALL-SPP is presented in details.•DM-ALL-SPP is applicable to different types of graphs.•DM-ALL-SPP can report any negative cycle.•DM-ALL-SPP is compared to the Floyd-Warshall algorithm.
Monochromatic Triangles, Triangle Listing and APSP Williams, Virginia Vassilevska; Xu, Yinzhan
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS),
2020-Nov.
Conference Proceeding
Odprti dostop
All-Pairs Shortest Paths (APSP) is one of the most basic problems in graph algorithms. Given an n -node directed or undirected graph with integer weights in \{-n^{c}, \ldots, n^{c}\} and no negative ...cycles, APSP asks to compute the shortest paths distance between every pair of vertices. The fastest known algorithm for APSP runs in n^{3}/2^{\Theta(\sqrt{\log n})} time Williams'14, and no truly subcubic time algorithms are known. One of the main hypotheses in fine-grained complexity is that APSP requires n^{3-o(1)} time. Another famous hypothesis in fine-grained complexity is that the 3SUM problem for n integers (which can be solved in O(n^{2}) time) requires n^{2-o(1)} time. Although there are no direct reductions between 3SUM and APSP, it is known that they are related: the (min, +)-convolution problem reduces in a fine-grained way to both, and both fine-grained reduce to the Exact Triangle problem. In this paper we find more relationships between these two problems and other basic problems. Pătraşcu had shown that under the 3SUM hypothesis the All-Edges Sparse Triangle problem in m -edge graphs requires m^{4/3-o(1)} time. The latter problem asks to determine for every edge e , whether e is in a triangle. It is equivalent to the problem of listing m triangles in an m -edge graph where m=-\tilde{O}(n^{1.5}) , and can be solved in O(m^{1.41}) time Alon et al.'97 with the current matrix multiplication bounds, and in \tilde{O}(m^{4/3}) time if \omega=2 . We show that one can reduce Exact Triangle to All-Edges Sparse Triangle, showing that All-Edges Sparse Triangle (and hence Triangle Listing) requires m^{4/3-o(1)} time also assuming the APSP hypothesis. This allows us to provide APSP-hardness for many dynamic problems that were previously known to be hard under the 3SUM hypothesis. We also consider the All-Edges Monochromatic Triangle problem. Via work of Lincoln et al.'20, our result on All-Edges Sparse Triangle implies that if the All-Edges Monochromatic Triangle problem has an O(n^{2.5-\varepsilon}) time algorithm for \epsilon > 0 , then both the APSP and 3SUM hypotheses are false. The fastest algorithm for All-Edges Monochromatic Triangle runs in \tilde{O}(n^{(3+\omega)/2}) time Vassilevska et al.'06, and our new reduction shows that if \omega=2 , this algorithm is best possible, unless 3SUM or APSP can be solved faster. Besides 3SUM, previously the only problems known to be fine-grained reducible to All-Edges Monochromatic Triangle were the seemingly easier problems directed unweighted APSP and Min-Witness Product Lincoln et al.'20. Our reduction shows that this problem is much harder. We also connect the problem to other "intermediate" problems, whose runtimes are between O(n^{\omega}) and O(n^{3}) , such as the Max-Min product problem.
A distributed network is modeled by a graph having n nodes (processors) and diameter D. We study the time complexity of approximating weighted (undirected) shortest paths on distributed networks with ...a O (log n) bandwidth restriction on edges (the standard synchronous CONGEST model). The question whether approximation algorithms help speed up the shortest paths and distance computation (more precisely distance computation) was raised since at least 2004 by Elkin (SIGACT News 2004). The unweighted case of this problem is well-understood while its weighted counterpart is fundamental problem in the area of distributed approximation algorithms and remains widely open. We present new algorithms for computing both single-source shortest paths (SSSP) and all-pairs shortest paths (APSP) in the weighted case.
Our main result is an algorithm for SSSP. Previous results are the classic O(n)-time Bellman-Ford algorithm and an Õ(n1/2+1/2k + D)-time (8k⌈log(k + 1)⌉ --1)-approximation algorithm, for any integer k ≥ 1, which follows from the result of Lenzen and Patt-Shamir (STOC 2013). (Note that Lenzen and Patt-Shamir in fact solve a harder problem, and we use Õ(·) to hide the O(poly log n) term.) We present an Õ (n1/2D1/4 + D)-time (1 + o(1))-approximation algorithm for SSSP. This algorithm is sublinear-time as long as D is sublinear, thus yielding a sublinear-time algorithm with almost optimal solution. When D is small, our running time matches the lower bound of Ω(n1/2 + D) by Das Sarma et al. (SICOMP 2012), which holds even when D=Θ(log n), up to a poly log n factor.
As a by-product of our technique, we obtain a simple Õ (n)-time (1+ o(1))-approximation algorithm for APSP, improving the previous Õ(n)-time O(1)-approximation algorithm following from the results of Lenzen and Patt-Shamir. We also prove a matching lower bound. Our techniques also yield an Õ(n1/2) time algorithm on fully-connected networks, which guarantees an exact solution for SSSP and a (2+ o(1))-approximate solution for APSP. All our algorithms rely on two new simple tools: light-weight algorithm for bounded-hop SSSP and shortest-path diameter reduction via shortcuts. These tools might be of an independent interest and useful in designing other distributed algorithms.
We design fast
deterministic
algorithms for distance computation in the
Congested Clique
model. Our key contributions include:
A
(
2
+
ϵ
)
-approximation for all-pairs shortest paths in
O
(
log
2
n
/
...ϵ
)
rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first
sub-polynomial
constant-factor approximation for APSP in this model.
A
(
1
+
ϵ
)
-approximation for multi-source shortest paths from
O
(
n
)
sources in
O
(
log
2
n
/
ϵ
)
rounds on weighted undirected graphs. This is the first
sub-polynomial
algorithm obtaining this approximation for a set of sources of polynomial size.
Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an
exact
single-source shortest paths algorithm for weighted undirected graphs in
O
~
(
n
1
/
6
)
rounds.
PDF
