Monochromatic Triangles, Triangle Listing and APSP
Monochromatic Triangles, Triangle Listing and APSP
复制标题
单色三角形、三角形列表和 APSP
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Yinzhan Xu
中科院分区：
文献类型：
--
作者：
V. V. Williams;Yinzhan Xu
全对最短路径（APSP）是图算法中最基本的问题之一。给定一个$n$节点有向图或无向图，其权值为$\{-n^{c}, \ldots, n^{c}\}$，且没有负环，APSP要求计算每对顶点之间的最短路径距离。已知最快的APSP算法运行时间为$n^{3}/2^{\Theta(\sqrt{\log n})}$ [Williams'14]，目前还没有真正的次立方时间算法。细粒度复杂性的一个主要假设是，APSP需要$n^{3-o(1)}$时间。细粒度复杂性的另一个著名假设是$n$整数的3SUM问题（可以在$O(n^{2})$时间内解决）需要$n^{2-o(1)}$时间。虽然3SUM和APSP之间没有直接的约简，但我们知道它们是相关的：(min, +)-卷积问题以细粒度的方式约简为两者，两者细粒度约简为精确三角形问题。在本文中，我们发现了这两个问题与其他基本问题之间的更多关系。picurtra<e:1>已经证明，在3SUM假设下，$m$ -边图的全边稀疏三角形问题需要$m^{4/3-o(1)}$时间。后一个问题要求确定对于每条边$e$, $e$是否在三角形中。它相当于在$m$边图中列出$m$三角形的问题，其中$m=-\tilde{O}(n^{1.5})$，并且可以在$O(m^{1.41})$时间内解决[Alon et al.'97]，使用当前矩阵乘法界，在$\tilde{O}(m^{4/3})$时间内解决$\omega=2$。我们证明了一个人可以将精确三角形约简为全边稀疏三角形，表明全边稀疏三角形（因此三角形列表）需要$m^{4/3-o(1)}$时间，也假设了APSP假设。这使我们能够为许多以前已知在3SUM假设下很难解决的动态问题提供apsp硬度。我们还考虑了全边单色三角形问题。通过[Lincoln et al.'20]的工作，我们在全边稀疏三角形上的结果表明，如果全边单色三角形问题对于$\epsilon > 0$具有$O(n^{2.5-\varepsilon})$时间算法，那么APSP和3SUM假设都是假的。全边单色三角形的最快算法运行时间为$\tilde{O}(n^{(3+\omega)/2})$ [Vassilevska et al.'06]，我们的新简化表明，如果$\omega=2$，该算法是最好的，除非3SUM或APSP可以更快地解决。除了3SUM之外，以前已知的唯一细粒度可约为全边单色三角形的问题是指向未加权APSP和Min-Witness积的看似更容易的问题[Lincoln et al.'20]。我们的简化表明，这个问题要难得多。我们还将该问题与其他“中间”问题联系起来，这些问题的运行时间在$O(n^{\omega})$和$O(n^{3})$之间，例如Max-Min乘积问题。
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.