论文标题
单色三角形，三角列表和APSP
Monochromatic Triangles, Triangle Listing and APSP
论文作者
论文摘要
细粒度复杂性的主要假设之一是，$ n $ node图的全对最短路径（APSP）需要$ n^{3-o（1）} $ time。另一个著名的假设是，$ n $整数的$ 3 $总问题需要$ n^{2-o（1）} $时间。尽管$ 3 $ sum和apsp之间没有直接减少，但众所周知，它们是相关的：存在问题，$（\ min，+）$ - 以细粒度减少到两者的方式，以及一个精确的三角形的问题，这两个问题都可以降低到。 在本文中，我们发现了这两个问题与其他基本问题之间的更多关系。 pătraşcu表明，在$ 3 $总假设下，全欧稀疏三角问题在$ m $ - 边缘图中需要$ m^{4/3-o（1）} $ time。后一个问题要求确定每个边缘$ e $，无论$ e $是否在三角形中。它等同于列出$ m $三角形在$ m $ - 边缘图中的问题，其中$ m = \ tilde {o}（n^{1.5}）$，并且可以在$ o（m^{1.41}）$ time [Alon等人[Alon et et al.'97]中求解。 $ \ tilde {o}（m^{4/3}）$时间如果$ω= 2 $。 我们表明，一个人可以将精确的三角形减少到稀疏的三角形，表明稀疏三角形（因此三角列表）需要$ m^{4/3-o（1）} $时间，也假设APSP假设也是如此。这使我们能够为许多动态问题提供APSP硬度，这些问题以前已知在$ 3 $总假设下很难。 我们还考虑了先前研究的All-Edges单色三角形问题。通过[Lincoln等人20]的作品，我们对全境的结果稀疏三角形意味着，如果All-Edges单色三角形问题具有$ O（n^{2.5-ε}）$ time Algorithm for $ε> 0 $，那么APSP和$ 3 $ sum sum sum sum sum sumpothes是假的。我们还将问题连接到其他``中间''问题，后者的运行时间在$ O（N^ω）$和$ O（N^3）$之间，例如Max-Min产品问题。
One of the main hypotheses in fine-grained complexity is that All-Pairs Shortest Paths (APSP) for $n$-node graphs requires $n^{3-o(1)}$ time. Another famous hypothesis is that the $3$SUM problem for $n$ integers requires $n^{2-o(1)}$ time. Although there are no direct reductions between $3$SUM 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ătraşcu had shown that under the $3$SUM 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 $ω=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 $3$SUM 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 $3$SUM hypotheses are false. 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.
