Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond
Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond
复制标题
通过短周期去除来近似 p 的硬度：周期检测、距离预言等等
DOI：
10.1145/3519935.3520066
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Zamir, Or
中科院分区：
文献类型：
--
作者：
Abboud, Amir;Bringmann, Karl;Khoury, Seri;Zamir, Or
我们提出了一种新的技术，有效地消除几乎所有的短周期图，而无意中删除其三角形。因此，即使在几乎无k-圈的图中，对于任何常数k ≥ 4，三角形的寻找问题也变得不容易。三角形的寻找是P中许多条件下界的基础，主要用于距离计算问题，并且在最坏情况下存在许多4-或5-圈一直是解决主要公开问题的障碍。是否存在预处理时间为m1 +o（1）、查询时间为mo（1）的距离预言机，它们能达到一个常数近似？现有的算法与这种理想的时间界限只能实现超常数近似因子，而只有3−因子被有条件地排除（Ptrajeccu，Roditty和Thorup; FOCS 2012）。我们证明了在3-SUM或APSP结构下，诺奥（1）近似是可能的.特别地，我们证明了k-逼近需要Ω（m1+1/ck）时间，这是紧到常数tc的.这个下界甚至适用于离线版本，在离线版本中，我们预先得到查询，并扩展到其他问题，如动态最短路径。4-圈问题：在细粒度复杂性中，一个臭名昭著的开放问题是从次二次甚至线性时间算法中建立任何令人惊讶的结果来检测图中的4-圈。这可以说是最简单的问题之一，没有近似线性时间算法，也没有条件下限。我们证明了所有k ≥ 4的叉循环检测需要Ω（m1.1194）时间，除非我们可以在O（n2−δ）时间内检测出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 almostk-cycle free graphs, for any constantk≥ 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 withm1+o(1)preprocessing time andmo(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 noO(1) approximations are possible, assuming the 3-SUM or APSP conjectures. In particular, we prove thatk-approximations require Ω(m1+1/ck) time, which is tight up to the constantc. The lower bound holds even for theofflineversion where we are given the queries in advance, and extends to other problems such as dynamic shortest paths.The4-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. This is arguably one of the simplest problems without a near-linear time algorithm nor a conditional lower bound. We prove that Ω(m1.1194) time is needed fork-cycle detection for allk≥ 4, unless we can detect a triangle in √n-degree graphs inO(n2−δ) time; a breakthrough that is not known to follow even from optimal matrix multiplication algorithms.
登录
查看更多内容
近乎最优的近似递减所有对最短路径
DOI：
10.1109/focs.2018.00025
发表时间：
2018
期刊：
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
S. Chechik
通讯作者：
S. Chechik
DOI：
10.1137/1.9781611977073.62
发表时间：
2022
期刊：
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022
影响因子：
--
作者：
Kadria, Avi;Roditty, Liam;Sidford, Aaron;Williams, Virginia Vassilevska;Zwick, Uri
通讯作者：
Zwick, Uri
用于构造 T 形扳手和具有拉伸 t 的路径的快速算法
DOI：
--
发表时间：
1993
期刊：
Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science
影响因子：
--
作者：
E. Cohen
通讯作者：
E. Cohen
DOI：
10.1137/090776573
发表时间：
2004
期刊：
45th Annual IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
L. Roditty;Uri Zwick
通讯作者：
Uri Zwick
未加权图的距离预言：打破具有恒定加性误差的二次障碍
DOI：
10.1007/978-3-540-70575-8_50
发表时间：
2008
期刊：
2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
影响因子：
--
作者：
Surender Baswana;Akshay Gaur;Sandeep Sen;Jayant Upadhyay
通讯作者：
Jayant Upadhyay