论文标题
通过短周期拆卸P中近似的硬度：循环检测，距离甲骨文以及超越
Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond
论文作者
论文摘要
我们提出了一种新技术，可有效地消除图中几乎所有短周期，而无需无意中删除其三角形。因此，即使在几乎$ k $ cycle的图表中，对于任何常数$ k \ geq 4 $，发现三角发现问题也不容易。 三角发现是P中许多条件下限的基础，主要用于距离计算问题，并且在最坏情况下存在许多$ 4 $ - 或$ 5 $ - 周期是解决重大开放问题的障碍。 近似硬度：是否有$ m^{1+o（1）} $预处理时间和$ m^{o（1）} $查询时间可实现恒定近似的时间？现有具有理想时间边界的现有算法只能实现超稳定近似因素，而有条件排除了$ 3-ε$的因素（Pătraşcu，Roditty和Thorup； focs 2012）。我们证明，假设$ 3 $ - sum或apsp的猜想，则可以使用$ O（1）$近似。特别是，我们证明$ k $ - approximations需要$ω（m^{1+1/ck}）$时间，这已经紧密到常数$ c $。下边界即使对于离线版本也可以提前给我们进行查询，并扩展到其他问题，例如动态最短路径。 $ 4 $循环问题：臭名昭著的颗粒复杂性的臭名昭著的开放问题是，从图中检测出$ 4 $ cycle的次级甚至线性时间算法会产生任何令人惊讶的后果。我们证明，对于所有$ k $ - 循环检测$ k \ geq 4 $，需要$ω（m^{1.1194}）$时间，除非我们可以在$ o（n^{2-Δ}）中以$ \ sqrt {n} $ graphs中的$ \ sqrt {n} $ - 度图检测到三角形;即使是从最佳矩阵乘法算法来看，也不知道的突破。
We present a new technique for efficiently removing almost all short cycles in a graph without unintentionally removing its triangles. Consequently, triangle finding problems do not become easy even in almost $k$-cycle free graphs, for any constant $k\geq 4$. Triangle finding is at the base of many conditional lower bounds in P, mainly for distance computation problems, and the existence of many $4$- or $5$-cycles in a worst-case instance had been the obstacle towards resolving major open questions. Hardness of approximation: Are there distance oracles with $m^{1+o(1)}$ preprocessing time and $m^{o(1)}$ query time that achieve a constant approximation? Existing algorithms with such desirable time bounds only achieve super-constant approximation factors, while only $3-ε$ factors were conditionally ruled out (Pătraşcu, Roditty, and Thorup; FOCS 2012). We prove that no $O(1)$ approximations are possible, assuming the $3$-SUM or APSP conjectures. In particular, we prove that $k$-approximations require $Ω(m^{1+1/ck})$ time, which is tight up to the constant $c$. The lower bound holds even for the offline version where we are given the queries in advance, and extends to other problems such as dynamic shortest paths. The $4$-Cycle problem: An infamous open question in fine-grained complexity is to establish any surprising consequences from a subquadratic or even linear-time algorithm for detecting a $4$-cycle in a graph. We prove that $Ω(m^{1.1194})$ time is needed for $k$-cycle detection for all $k\geq 4$, unless we can detect a triangle in $\sqrt{n}$-degree graphs in $O(n^{2-δ})$ time; a breakthrough that is not known to follow even from optimal matrix multiplication algorithms.
