Monochromatic Triangles, Triangle Listing and APSP

All-Pairs Shortest Paths (APSP) is one of the most basic problems in graph algorithms. In one of the most general variants of the problem, one is given an n-node directed or undirected graph with integer weights in -n c , . . . , n c and no negative cycles and one needs to compute the shortest paths distance between every pair of vertices. A central question in graph algorithms is how fast APSP can be solved. The fastest known algorithm runs in n 3 /2 Θ( √ log n) time [Williams'14], and no truly subcubic time algorithms are known.

One of the main hypotheses in fine-grained complexity is that this problem 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: there is a problem, (min, +)-convolution that reduces in a fine-grained way to both, and a problem Exact Triangle that both fine-grained reduce to.

In this paper we find more relationships between these two problems and other basic problems. Pȃtras ¸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 = Õ(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 Õ(m 4/3 ) time if ω = 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 previously studied 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-ε ) time algorithm for ε > 0, then both the APSP and 3SUM hypotheses are false. The fastest algorithm for All-Edges Monochromatic Triangle runs in Õ(n (3+ω)/2 ) time [Vassilevska et al.'06], and our new reduction shows that if ω = 2, this algorithm is best possible, unless 3SUM or APSP can be solved faster. Besides 3SUM, previously, the only problems known to be finegrained reducible to All-Edges Monochromatic Triangle were the seemingly easier problems directed unweighted APSP and Min-Witness Product [Lincoln et al.'20]. Our new reduction shows that this problem is much harder. We also connect the problem to other "intermediate" problems, whose runtimes are between O(n ω ) and O(n 3 ), such as the Max-Min product problem.