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.
Full text
Available for:
IZUM, KILJ, NUK, PILJ, SAZU, UL, UM, UPUK
Shortest paths are representative of discrete geodesic distances in graphs, and many descriptors of networks depend on their counting. In multiplex networks, this counting is radically important to ...quantify the switch between layers and it has crucial implications in the transportation efficiency and congestion processes. Here we present a mathematical approach to the computation of the joint distribution of distance and multiplicity (degeneration) of shortest paths in multiplex networks, and exploit its relation to congestion processes. The results allow us to approximate semi-analytically the onset of congestion in multiplex networks as a function of the congestion of its layers.
Computing driving directions has motivated many shortest path algorithms based on preprocessing. Given a graph, the preprocessing stage computes a modest amount of auxiliary data, which is then used ...to speed up online queries. In practice, the best algorithms have storage overhead comparable to the graph size and answer queries very fast, while examining a small fraction of the graph. In this article, we complement the experimental evidence with the first rigorous proofs of efficiency for some of the speedup techniques developed over the past decade or variations thereof. We define highway dimension, which strengthens the notion of doubling dimension. Under the assumption that the highway dimension is low (at most polylogarithmic in the graph size), we show that, for some algorithms or their variants, preprocessing can be implemented in polynomial time, the resulting auxiliary data increases the storage requirements by a polylogarithmic factor, and queries run in polylogarithmic time. This gives a unified explanation for the performance of several seemingly different approaches. Our best bounds are based on a result that may be of independent interest: we show that unique shortest paths induce set systems of low VC-dimension, which makes them combinatorially simple.
Full text
Available for:
IZUM, KILJ, NUK, PILJ, SAZU, UL, UM, UPUK
Thorup and Zwick 1 introduced the notion of approximate distance oracles, a data structure that produces for an n-vertex, m-edge weighted undirected graph G=(V,E), distance estimations in constant ...query time. They presented a distance oracle of size O(kn1+1/k) that given a pair of vertices u,v∈V at distance d(u,v) produces in O(k) time an estimation that is bounded by (2k−1)d(u,v), i.e., a (2k−1)-multiplicative approximation (stretch). Thorup and Zwick 1 presented also a lower bound based on the girth conjecture of Erdős.
For sparse unweighted graphs (i.e., m=O˜(n)) the lower bound does not apply. Pǎtraşcu and Roditty 2 used the sparsity of the graph and obtained a distance oracle that uses O˜(n5/3) space, has O(1) query time and a stretch of 2. Pǎtraşcu et al. 3 presented infinitely many distance oracles with fractional stretch factors that for graphs with m=O˜(n) converge exactly to the integral stretch factors and the corresponding space bound of Thorup and Zwick.
It is not known, however, whether graph sparsity can help to get a stretch which is better than (2k−1) using only O˜(kn1+1/k) space. In this paper we answer this open question and prove a separation between sparse and dense graphs by showing that using sparsity it is possible to obtain better stretch/space tradeoffs than those of Thorup and Zwick. We show that for every k≥2 there is a distance oracle of size O˜(km1+1/k) that produces in O(k) time an estimation d⁎(u,v) that satisfies d(u,v)≤d⁎(u,v)≤(2k−1)d(u,v)−4, for k>2, and d(u,v)≤d⁎(u,v)≤3d(u,v)−2, for k=2.
Another contribution of this paper is a refined stretch analysis of Thorup and Zwick distance oracles that allows us to obtain a better understanding of this important data structure. We present simple conditions for every w∈V that characterize the exact scenarios in which every query that involves w produces an estimation of stretch strictly better than 2k−1, even in the case of dense graphs. We complement this contribution with an experiment on real world graphs. The main finding in the experiment is that different real world graphs are likely to satisfy the required conditions and hence the stretch of Thorup and Zwick distance oracles is much better than its worst case bound in these real world graphs.
•Graph sparsity can help to get space-stretch tradeoffs for Distance Oracle which are strictly better than Thorup and Zwick space-stretch tradeoffs for general undirected graphs.•A refined stretch analysis of Thorup and Zwick Distance Oracle that characterizes several cases in which the stretch is strictly better than 2k−1.•An experiment on real world graphs shows that the cases characterized in the refined stretch analysis are quite frequent, and thus, in many real world graphs, the actual stretch is much better than the worst case stretch bound.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Let G=(V,E) be an unweighted undirected graph with n vertices and m edges. Dor, Halperin, and Zwick FOCS 1996, SICOMP 2000 presented an (min{n3/2m1/2,n7/3 })-time algorithm that computes estimated ...distances with an additive approximation of 2 without using Fast Matrix Multiplication (FMM). Recently, Deng, Kirkpatrick, Rong, V. Williams and Zhong ICALP 2022 improved the running time for dense graphs to (n2.29)-time, using FMM, where an exact solution can be computed with FMM in (nω) time (ω < 2.37286) using Seidel’s algorithm.
Since an additive 2 approximation is also a multiplicative 2 approximation, computing an additive 2 approximation is at least as hard as computing a multiplicative 2 approximation. Thus, computing a multiplicative 2 approximation might be an easier problem. Nevertheless, more than two decades after the paper of Dor, Halperin, and Zwick was first published, no faster algorithm for computing multiplicative 2 approximation in dense graphs is known, rather then simply computing an additive 2 approximation.
In this paper we present faster algorithms for computing a multiplicative 2 approximation without FMM. We show that in (min{ n1/2m ,n9/4 }) time it is possible to compute a multiplicative 2 approximation. For distances at least 4 we can get an even faster algorithm that in (min{ n7/4m1/4,n11/5}) expected time computes a multiplicative 2 approximation.
Our algorithms are obtained by a combination of new ideas that take advantage of a careful new case analysis of the additive approximation algorithms of Dor, Halperin, and Zwick. More specifically, one of the main technical contributions we made is an analysis of the algorithm of Dor, Halperin, and Zwick that reveals certain cases in which their algorithm produces improved additive approximations without any modification. This analysis provides a full characterization of the instances for which it is harder to obtain an improved approximation. Using more ideas we can take care of some of these harder cases and to obtain an improved additive approximation also for them. Our new analysis, therefore, serves as a starting point for future research either on improved upper bounds or on conditional lower bounds.
We study the problem of path computation in Cayley Graphs (CG) from an approach of word processing in groups. This approach consists in encoding the topological structure of CG in an automaton called ...Diff, then techniques of word processing are applied for computing the shortest paths. We present algorithms for computing the K-shortest paths, the shortest disjoint paths and the shortest path avoiding a set of nodes and edges. For any CG with diameter D, the time complexity of the proposed algorithms is O(KD|Diff|), where |Diff| denotes the size of Diff. We show that our proposal outperforms the state of art of topology-agnostic algorithms for disjoint shortest paths and stays competitive with respect to proposals for specific families of CG. Therefore, the proposed algorithms set a base in the design of adaptive and low-complexity routing schemes for networks whose interconnections are defined by CG.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Finding Top-k Shortest Paths with Diversity Liu, Huiping; Jin, Cheqing; Yang, Bin ...
IEEE transactions on knowledge and data engineering,
03/2018, Volume:
30, Issue:
3
Journal Article
Peer reviewed
The classical K Shortest Paths (KSP) problem, which identifies the k shortest paths in a directed graph, plays an important role in many application domains, such as providing alternative paths for ...vehicle routing services. However, the returned k shortest paths may be highly similar, i.e., sharing significant amounts of edges, thus adversely affecting service qualities. In this paper, we formalize the K Shortest Paths with Diversity (KSPD) problem that identifies top-k shortest paths such that the paths are dissimilarwith each other and the total length of the paths is minimized. We first prove that the KSPD problem is NP-hard and then propose a generic greedy framework to solve the KSPD problem in the sense that (1) it supports a wide variety of path similarity metrics which are widely adopted in the literature and (2) it is also able to efficiently solve the traditional KSP problem if no path similarity metric is specified. The core of the framework includes the use of two judiciously designed lower bounds, where one is dependent on and the other one is independent on the chosen path similarity metric, which effectively reduces the search space and significantly improves efficiency. Empirical studies on five real-world and synthetic graphs and five different path similarity metrics offer insight into the design properties of the proposed general framework and offer evidence that the proposed lower bounds are effective.
PDF
