New hardness results for planar graph problems in p and an algorithm for sparsest cut
New hardness results for planar graph problems in p and an algorithm for sparsest cut
复制标题
DOI：
10.1145/3357713.3384310
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Amir Abboud;Vincent Cohen-Addad;P. Klein
中科院分区：
文献类型：
--
作者：
Amir Abboud;Vincent Cohen-Addad;P. Klein
稀疏割问题是一个基本的优化问题，已被广泛研究。对于平面输入的问题是在P和可以解决在n（n 3）的时间，如果所有的顶点权重是1。尽管付出了大量的努力，最好的算法可以追溯到90年代初，只能实现O（log n）-近似在n（n）时间或3.5-近似在n（n 2）时间[Rao，STOC 92]。我们的主要结果是在（min，+）-卷积猜想下，即使在具有单位顶点权重的平面图中，稀疏割的Ω（n 2−ε）下界，表明近似在近线性时间范围内是不可避免的。为了补充下限，我们提供了一个3.3近似在近线性时间，提高了25岁的结果饶在时间和精度。我们还表明，我们的下限是不远处的最佳观察一个精确的算法，运行时间为n（n 5/2）的改进后，公园和菲利普斯[STOC 93]的算法的n（n 3）。我们的下界完成了一个反复提出的挑战，是第一个细粒度的下界自然平面图的问题，在P.我们的建设，我们证明了近二次下界SETH下的变体的最接近的一对问题的平面图，并使用它们来表明，流行的平均链接过程层次聚类不能模拟在真正的次二次时间。在我们的建设的核心是一个钻石般的小工具，也解决了分布式平面网络中的直径的复杂性。我们证明了在CONGET模型中计算网络的加权直径所需的通信轮数的Ω（n/ log n）下界，即使底层图是平面的，并且所有节点彼此相距D = 4跳。这是平面分布设置中的第一个poly（n）下界，并且它补充了Li和Parter [STOC 2019]针对（精确）未加权直径和（1 + ε）近似加权直径的最近poly（D，log n）上界。
The Sparsest Cut is a fundamental optimization problem that have been extensively studied. For planar inputs the problem is in P and can be solved in Õ(n 3 ) time if all vertex weights are 1. Despite a significant amount of effort, the best algorithms date back to the early 90’s and can only achieve O(log n)-approximation in Õ(n) time or 3.5-approximation in Õ(n 2 ) time [Rao, STOC92]. Our main result is an Ω(n 2−ε ) lower bound for Sparsest Cut even in planar graphs with unit vertex weights, under the (min, +)-Convolution conjecture, showing that approxima- tions are inevitable in the near-linear time regime. To complement the lower bound, we provide a 3.3-approximation in near-linear time, improving upon the 25-year old result of Rao in both time and accuracy. We also show that our lower bound is not far from optimal by observing an exact algorithm with running time Õ(n 5/2 ) improving upon the Õ(n 3 ) algorithm of Park and Phillips [STOC93]. Our lower bound accomplishes a repeatedly raised challenge by being the first fine-grained lower bound for a natural planar graph problem in P. Building on our construction we prove near-quadratic lower bounds under SETH for variants of the closest pair problem in planar graphs, and use them to show that the popular Average-Linkage procedure for Hierarchical Clustering cannot be simulated in truly subquadratic time. At the core of our constructions is a diamond-like gadget that also settles the complexity of Diameter in distributed planar networks. We prove an Ω(n/ log n) lower bound on the number of communication rounds required to compute the weighted diameter of a network in the CONGET model, even when the underlying graph is planar and all nodes are D = 4 hops away from each other. This is the first poly(n) lower bound in the planar-distributed setting, and it complements the recent poly(D, log n) upper bounds of Li and Parter [STOC 2019] for (exact) unweighted diameter and for (1 + ε) approximate weighted diameter.