论文标题
P平面图问题的新硬度结果和最稀少的算法
New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut
论文作者
论文摘要
最稀少的削减是经过广泛研究的基本优化问题。对于平面输入，问题在$ p $中，并且可以在$ \ tilde {o}（n^3）$ time中解决，如果所有顶点权重为$ 1 $。尽管付出了很大的努力，但最好的算法可以追溯到90年代初期，并且只能在$ o（\ log n）$ - $ \ tilde {o}（o}（n）$ time或$ \ tilde {o}（o}（o}（o}（n^2）$ time [rao，stoc92）中，以$ \ tilde {o}（n）$时间近似。我们的主要结果是$ω（n^{2-ε}）$下限，即使在带有单位顶点权重的平面图中，在$（min，+）$ - 卷积的猜想下，也表明在接近线性的时间范围内不可避免地近似是不可避免的。为了补充下限，我们在接近线性的时间内提供了一个恒定的因子近似值，从而改善了时间和准确性的25岁rao结果。 我们的下限是通过成为P.的自然平面图问题的第一个细粒度下限，这是我们的下限挑战。此外，我们证明了Seth在SETH下的近乎二次的下限，用于平面图中最接近的一对问题的变体，并使用它们来表明在真正的层次聚类中，无法在真正的层次聚类中进行真正的平均链接程序。 我们证明了一个$ω（N/\ log {n}）$在交流弹的数量上降低了交流弹的数量，即使在colest模型中计算网络的加权直径，即使基础图是平面，并且所有节点均为$ d = 4 $ hops。这是平面分布式设置中的第一个poly（$ n $） + $ω（d）$下限，它补充了最近的poly $（d，\ log {n}）$ li and parter [stoc 2019]的上限[stoc 2019]（excceck）未加权直径，并且（$ 1 +ε$）的重量加权直径（$ 1 +ε$）。
The Sparsest Cut is a fundamental optimization problem that has been extensively studied. For planar inputs the problem is in $P$ and can be solved in $\tilde{O}(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 $\tilde{O}(n)$ time or a constant factor approximation in $\tilde{O}(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 approximations are inevitable in the near-linear time regime. To complement the lower bound, we provide a constant factor approximation in near-linear time, improving upon the 25-year old result of Rao in both time and accuracy. Our lower bound accomplishes a repeatedly raised challenge by being the first fine-grained lower bound for a natural planar graph problem in P. Moreover, 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. 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 CONGEST 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$) + $ω(D)$ 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.
