A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
复制标题
一种新的递减单源最短路径算法及其在顶点容量流和切割问题中的应用
DOI：
10.1145/3313276.3316320
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
S. Khanna
中科院分区：
文献类型：
--
作者：
Julia Chuzhoy;S. Khanna
我们研究了顶点单源最短路径（SSSP）问题：给定无向图G =（v，e），其边缘的长度ℓ（e）≥1≥1≥1≥1≥1，并且经历了顶点缺失，我们需要支持G：给定的顶点V中的（近似）最短路径查询，返回将S连接到V的路径，其长度最多是最短的此路径的长度，其中є是给定的。准确性参数。 Graph G经历Edge删除。 L是任何边缘的最大长度，这些改进的结果是随机的算法，这些算法明显地超越了明显的广告限制，最近，伯恩斯坦和伯恩斯坦和车臣设计了问题的确定性算法（N2LOGL），根据定义，不幸的是，他们的算法会引入一个新的限制，即，他们只能返回最短路径的大约长度，而不是路径本身的许多应用程序。 ，包括本文中考虑的内容完全要求算法本身返回大约最短的路径，而不仅仅是它们的长度，并且它与自适应广告相比，我们的主要结果是总计的随机算法。预期的更新时间O（N2+O（1）Logl），在期望中响应（NLOGL）时间中的每个最短路径查询，返回（1+є） - 适当的最短路径。 。在g中的查询顶点，我们使用我们的结果来获得顶点ssss和O（log4n） - 最稀少的剪切问题的顶点版本的Approximation算法，而预期的运行时间N2+O（1）会在M =ω的情况下改善这些问题的先前最佳已知算法.5 + O（1））。
We study the vertex-decremental Single-Source Shortest Paths (SSSP) problem: given an undirected graph G=(V,E) with lengths ℓ(e)≥ 1 on its edges that undergoes vertex deletions, and a source vertex s, we need to support (approximate) shortest-path queries in G: given a vertex v, return a path connecting s to v, whose length is at most (1+є) times the length of the shortest such path, where є is a given accuracy parameter. The problem has many applications, for example to flow and cut problems in vertex-capacitated graphs. Decremental SSSP is a fundamental problem in dynamic algorithms that has been studied extensively, especially in the more standard edge-decremental setting, where the input graph G undergoes edge deletions. The classical algorithm of Even and Shiloach supports exact shortest-path queries in O(mn) total update time. A series of recent results have improved this bound to O(m1+o(1)logL), where L is the largest length of any edge. However, these improved results are randomized algorithms that assume an oblivious adversary. To go beyond the oblivious adversary restriction, recently, Bernstein, and Bernstein and Chechik designed deterministic algorithms for the problem, with total update time Õ(n2logL), that by definition work against an adaptive adversary. Unfortunately, their algorithms introduce a new limitation, namely, they can only return the approximate length of a shortest path, and not the path itself. Many applications of the decremental SSSP problem, including the ones considered in this paper, crucially require both that the algorithm returns the approximate shortest paths themselves and not just their lengths, and that it works against an adaptive adversary. Our main result is a randomized algorithm for vertex-decremental SSSP with total expected update time O(n2+o(1)logL), that responds to each shortest-path query in Õ(nlogL) time in expectation, returning a (1+є)-approximate shortest path. The algorithm works against an adaptive adversary. The main technical ingredient of our algorithm is an Õ(|E(G)|+ n1+o(1))-time algorithm to compute a core decomposition of a given dense graph G, which allows us to compute short paths between pairs of query vertices in G efficiently. We use our result for vertex-decremental SSSP to obtain (1+є)-approximation algorithms for maximum s-t flow and minimum s-t cut in vertex-capacitated graphs, in expected time n2+o(1), and an O(log4n)-approximation algorithm for the vertex version of the sparsest cut problem with expected running time n2+o(1). These results improve upon the previous best known algorithms for these problems in the regime where m= ω(n1.5 + o(1)).