Tight Hardness for Shortest Cycles and Paths in Sparse Graphs
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs
复制标题
稀疏图中最短循环和路径的严格硬度
DOI：
10.1137/1.9781611975031.91
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Williams, R.
中科院分区：
文献类型：
--
作者：
Lincoln, A.;Vassilevska Williams, V.;Williams, R.
细粒度约简建立了n结点赋权图上的最短圈、所有对最短路（APSP）、半径、替换路、次最短路等许多具有n（n ~ 3）时间算法的核心问题之间的等价关系，这些问题也有m边结点赋权图上的n（n ~ n）时间算法，并且这些算法具有更广泛的适用性。当m <<n2时，这些边界是最优的吗？本文从边权图的最小权（2 <$+ 1）-团问题需要n2 <$+1-o（1）时间的假设出发，证明了对于m = Θ（n1+1/<$）形式的所有稀疏性，不存在O（n2+ mn 1-ε）时间算法ε> 0对于以下任一问题·有向加权图中的最小权（2 n + 1）-圈，·有向加权图中的最短圈，·有向或无向加权图中的APSP，·有向或无向加权图中的偏度（或偏心率），·有向或无向加权图的维纳指数，·有向加权图中的替换路径，·有向加权图中的第二最短路径，·有向加权图中给定节点的介数中心性。我们从稠密图问题的困难性出发，证明了各种稀疏图问题的困难性。我们的结果也导致了新的条件下界从几个相关的假设，包括k-圈，最短圈，半径，维纳指数和APSP的无权稀疏图问题。
Fine-grained reductions have established equivalences between many core problems withÕ(n3)-time algorithms onn-node weighted graphs, such as Shortest Cycle, All-Pairs Shortest Paths (APSP), Radius, Replacement Paths, Second Shortest Paths, and so on. These problems also haveÕ(mn)-time algorithms onm-edgen-node weighted graphs, and such algorithms have wider applicability. Are thesemnbounds optimal whenm<<n2?Starting from the hypothesis that the minimum weight (2ℓ+ 1)-Clique problem in edge weighted graphs requiresn2ℓ+1–o(1)time, we prove that for all sparsities of the formm= Θ(n1+1/ℓ), there is noO(n2+mn1–ε) time algorithm forε> 0 foranyof the below problems• Minimum Weight (2ℓ+ 1)-Cycle in a directed weighted graph,• Shortest Cycle in a directed weighted graph,• APSP in a directed or undirected weighted graph,• Radius (or Eccentricities) in a directed or undirected weighted graph,• Wiener index of a directed or undirected weighted graph,• Replacement Paths in a directed weighted graph,• Second Shortest Path in a directed weighted graph,• Betweenness Centrality of a given node in a directed weighted graph.That is, we prove hardness for a variety of sparse graph problems from the hardness of a dense graph problem. Our results also lead to new conditional lower bounds from several related hypothesis for unweighted sparse graph problems includingk-cycle, shortest cycle, Radius, Wiener index and APSP.
登录
查看更多内容
更快的更换路径
DOI：
--
发表时间：
2010
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
V. V. Williams
通讯作者：
V. V. Williams
DOI：
--
发表时间：
2016
期刊：
arXiv.org
影响因子：
--
作者：
U. Agarwal;V. Ramachandran
通讯作者：
V. Ramachandran
实加权稀疏图的更快的全对最短路径算法
DOI：
--
发表时间：
2002
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
Seth Pettie
通讯作者：
Seth Pettie
通过 capped k-walks 更快地找到均匀循环
DOI：
--
发表时间：
2017
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Søren Dahlgaard;M. B. T. Knudsen;Morten Stöckel
通讯作者：
Morten Stöckel
最小权重循环和三角形：等价物和算法
DOI：
--
发表时间：
2011
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
L. Roditty;V. V. Williams
通讯作者：
V. V. Williams