In this paper we carefully combine Fredman's trick [SICOMP'76] and Matousek's approach for dominance product [IPL'91] to obtain powerful results in fine-grained complexity:
The 3SUM hypothesis, the APSP hypothesis and SETH are the three main hypotheses in fine-grained complexity. So far, within the area, the first two hypotheses have mainly been about integer inputs in the Word RAM model of computation. The "Real APSP" and "Real 3SUM" hypotheses, which assert that the APSP and 3SUM hypotheses hold for real-valued inputs in a reasonable version of the Real RAM model, are even more believable than their integer counterparts.
Under the very believable hypothesis that at least one of the Integer 3SUM hypothesis, Integer APSP hypothesis or SETH is true, Abboud, Vassilevska W. and Yu [STOC 2015] showed that a problem called Triangle Collection requires n^{3-o(1)} time on an n-node graph.
Our main result is a nontrivial lower bound for a slight generalization of Triangle Collection, called All-Color-Pairs Triangle Collection, under the even more believable hypothesis that at least one of the Real 3SUM, the Real APSP, and the OV hypotheses is true. Combined with slight modifications of prior reductions, we obtain polynomial conditional lower bounds for problems such as the (static) ST-Max Flow problem and dynamic Max Flow, now under the new weaker hypothesis.
Our main result is built on the following two lines of reductions.
Given a graph with n vertices and real edge weights in [0,1], we investigate an approximate version of the standard all-pairs shortest paths (APSP) problem where distances are estimated with additive error at most epsilon. Yuster (2012) introduced this natural variant of approximate APSP, and presented an algorithm for directed graphs running in O~(n^{(3+omega)/2}) < O(n^{2.687}) time for an arbitrarily small constant epsilon > 0, where omega denotes the matrix multiplication exponent. We give a faster algorithm for undirected graphs running in O~(n^{(3+omega^2)/(omega+1)}) < O(n^{2.559}) time for any constant epsilon > 0. If omega = 2, the time bound is O~(n^{7/3}), matching a previous result for undirected graphs by Dor, Halperin, and Zwick (2000) which only guaranteed additive error at most 2.
All-Pairs Shortest Paths (APSP) is one of the most well studied problems in graph algorithms. This paper studies several variants of APSP in unweighted graphs or graphs with small integer weights.
APSP with small integer weights in undirected graphs [Seidel'95, Galil and Margalit'97] has an O~(n^omega) time algorithm, where omega < 2.373 is the matrix multiplication exponent. APSP in directed graphs with small weights however, has a much slower running time that would be Omega(n^{2.5}) even if omega = 2 [Zwick'02]. To understand this n^{2.5} bottleneck, we build a web of reductions around directed unweighted APSP. We show that it is fine-grained equivalent to computing a rectangular Min-Plus product for matrices with integer entries; the dimensions and entry size of the matrices depend on the value of omega. As a consequence, we establish an equivalence between APSP in directed unweighted graphs, APSP in directed graphs with small (O~(1)) integer weights, All-Pairs Longest Paths in DAGs with small weights, c-Red-APSP in undirected graphs with small weights, for any c >= 2 (computing all-pairs shortest path distances among paths that use at most c red edges), #_{<= c}APSP in directed graphs with small weights (counting the number of shortest paths for each vertex pair, up to c), and approximate APSP with additive error c in directed graphs with small weights, for c <= O~(1).
We also provide fine-grained reductions from directed unweighted APSP to All-Pairs Shortest Lightest Paths (APSLP) in undirected graphs with {0,1} weights and #_{mod c}APSP in directed unweighted graphs (computing counts mod c), thus showing that unless the current algorithms for APSP in directed unweighted graphs can be improved substantially, these problems need at least Omega(n^{2.528}) time.
We complement our hardness results with new algorithms. We improve the known algorithms for APSLP in directed graphs with small integer weights (previously studied by Zwick [STOC'99]) and for approximate APSP with sublinear additive error in directed unweighted graphs (previously studied by Roditty and Shapira [ICALP'08]). Our algorithm for approximate APSP with sublinear additive error is optimal, when viewed as a reduction to Min-Plus product. We also give new algorithms for variants of #APSP (such as #_{<= U}APSP and #_{mod U}APSP for U <= n^{O~(1)}) in unweighted graphs, as well as a near-optimal O~(n^3)-time algorithm for the original #APSP problem in unweighted graphs (when counts may be exponentially large). This also implies an O~(n^3)-time algorithm for Betweenness Centrality, improving on the previous O~(n^4) running time for the problem. Our techniques also lead to a simpler alternative to Shoshan and Zwick�s algorithm [FOCS'99] for the original APSP problem in undirected graphs with small integer weights.
We present an algorithm that computes a (1+epsilon)-approximation of the diameter of a weighted, undirected planar graph of n vertices with non-negative edge lengths in O(n log n (log n + (1/epsilon)^5)) expected time, improving upon the O(n ((1/epsilon)^4 log^4 n + 2^{O(1/epsilon)}))-time algorithm of Weimann and Yuster [ICALP 2013]. Our algorithm makes two improvements over that result: first and foremost, it replaces the exponential dependency on 1/epsilon with a polynomial one, by adapting and specializing Cabello's recent abstract-Voronoi-diagram-based technique [SODA 2017] for approximation purposes; second, it shaves off two logarithmic factors by choosing a better sequence of error parameters during recursion.
Moreover, using similar techniques, we improve the (1+epsilon)-approximate distance oracle of Gu and Xu [ISAAC 2015] by first replacing the exponential dependency on 1/epsilon on the preprocessing time and space with a polynomial one and second removing a logarithmic factor from the preprocessing time.
We address the All-Pairs Shortest Paths (APSP) problem for a number of unweighted, undirected geometric intersection graphs. We present a general reduction of the problem to static, offline intersection searching (specifically detection). As a consequence, we can solve APSP for intersection graphs of n arbitrary disks in O(n^2 log n) time, axis-aligned line segments in O(n^2 loglog n) time, arbitrary line segments in O(n^{7/3} log^{1/3} n) time, d-dimensional axis-aligned boxes in O(n^2 log^{d-1.5} n) time for d >= 2, and d-dimensional axis-aligned unit hypercubes in O(n^2 loglog n) time for d=3 and O(n^2 log^{d-3} n) time for d >= 4.
In addition, we show how to solve the Single-Source Shortest Paths (SSSP) problem in unweighted intersection graphs of axis-aligned line segments in O(n log n) time, by a reduction to dynamic orthogonal point location.
We revisit the orthogonal range searching problem and the exact l_infinity nearest neighbor searching problem for a static set of n points when the dimension d is moderately large. We give the first data structure with near linear space that achieves truly sublinear query time when the dimension is any constant multiple of log n. Specifically, the preprocessing time/space is O(n^{1+delta}) for any constant delta > 0, and the expected query time is n^{1 - 1/O(c log c)}. The data structure is simple and is based on a new "augmented, randomized, lopsided" variant of k-d trees. It matches (in fact, slightly improves) the performance of previous combinatorial algorithms that work only in the case of offline queries [Impagliazzo, Lovett, Paturi, and Schneider (2014)
and Chan (SODA'15)]. It leads to faster combinatorial algorithms for all-pairs shortest paths in general weighted graphs and rectangular Boolean matrix multiplication.In the offline case, we show that the problem can be reduced to the Boolean orthogonal vectors problem and thus admits an n^{2 - 1/O(log c)}-time non-combinatorial algorithm [Abboud, Williams, and Yu (SODA'15)]. This reduction is also simple and is based on range trees.
Finally, we use a similar approach to obtain a small improvement to Indyk's data structure [FOCS'98] for approximate l_infinity nearest neighbor search when d=c log n.
In this paper we study the all-pairs shortest paths problem in (unweighted) unit-disk graphs. The previous best solution for this problem required O(n^2 log n) time, by running the O(n log n)-time single-source shortest path algorithm of Cabello and Jejcic (2015) from every source vertex, where n is the number of vertices. We not only manage to eliminate the logarithmic factor, but also obtain the first (slightly) subquadratic algorithm for the problem, running in O(n^2 sqrt{loglog n/log n}) time. Our algorithm computes an implicit representation of all the shortest paths, and, in the same amount of time, can also compute the diameter of the graph.
We show how to solve all-pairs shortest paths on n nodes in deterministic n^3 / 2^{Omega(sqrt{log n})} time, and how to count the pairs of orthogonal vectors among n 0-1 vectors in d = c log n dimensions in deterministic n^{2 - 1/O(log c)} time. These running times essentially match the best known randomized algorithms of (Williams, STOC'14) and (Abboud, Williams, and Yu, SODA 2015) respectively, and the ability to count was open even for randomized algorithms. By reductions, these two results yield faster deterministic algorithms for many other problems. Our techniques can also be used to count k-SAT assignments on n variable formulas in 2^{n - n/O(k)} time, roughly matching the best known running times for detecting satisfiability and resolving an open problem of Santhanam (2013).
A key to our constructions is an efficient way to deterministically simulate certain probabilistic polynomials critical to the algorithms of prior work, applying epsilon-biased sets and modulus-amplifying polynomials.
We present a new combinatorial algorithm for Boolean matrix multiplication that runs in O(n^3 (loglog n)^3 / log^3 n) time. This improves the previous combinatorial algorithm by Bansal and Williams [FOCS'09] that runs in O(n^3 (loglog n)^2 / log^{9/4} n) time. Whereas Bansal and Williams' algorithm uses regularity lemmas for graphs, the new algorithm is simple and uses entirely elementary techniques: table lookup, word operations, plus a deceptively straightforward divide-and-conquer.
Our algorithm is in part inspired by a recent result of Impagliazzo, Lovett, Paturi, and Schneider (2014) on a different geometric problem, offline dominance range reporting; we improve their analysis for that problem as well.
In the first part of the paper, we reexamine the all-pairs shortest paths (APSP) problem and present a new algorithm with running time approaching O(n^3 log^3log n / log^2 n), which improves all known algorithms for general real-weighted dense graphs.
In the second part of the paper, we use fast matrix multiplication to obtain truly subcubic APSP algorithms for a large class of "geometrically weighted" graphs, where the weight of an edge is a function of the coordinates of its vertices. For example, for graphs embedded in Euclidean space of a constant dimension d, we obtain a time bound near O(n^{3-(3-w)/(2d+4)}), where w < 2.376; in two dimensions, this is O(n^{2.922}). Our framework greatly extends the previously considered case of small-integer-weighted graphs, and incidentally also yields the first truly subcubic result (near O(n^{3-(3-w)/4}) = O(n^{2.844}) time) for APSP in real-vertex-weighted graphs, as well as an improved result (near O(n^{(3+w)/2}) = O(n^{2.688}) time) for the all-pairs lightest shortest path problem for small-integer-weighted graphs.
We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is measured according to the l_p norm of the vector of distances between pairs of beads from opposite necklaces in the best perfect matching. We show surprisingly different results for p=1, p=2, and p=infty. For p=2, we reduce the problem to standard convolution, while for p=infty and p=1, we reduce the problem to (min,+) convolution and (median,+) convolution. Then we solve the latter two convolution problems in subquadratic time, which are interesting results in their own right. These results shed some light on the classic sorting X+Y problem, because the convolutions can be viewed as computing order statistics on the antidiagonals of the X+Y matrix. All of our algorithms run in o(n^2) time, whereas the obvious algorithms for these problems run in Theta(n^2) time.
We revisit the all-pairs-shortest-paths problem for an unweighted undirected graph with n vertices and m edges. We present new algorithms with the following running times:
We describe an O(n^3 / log n)-time algorithm for the all-pairs-shortest-paths problem for a real-weighted directed graph with n vertices. This slightly improves a series of previous, slightly subcubic algorithms by Fredman (1976), Takaoka (1992), Dobosiewicz (1990), Han (2004), Takaoka (2004), and Zwick (2004). The new algorithm is surprisingly simple and different from previous ones.
The documents contained in this directory are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.