Breaking quadratic time for small vertex connectivity and an approximation scheme
Breaking quadratic time for small vertex connectivity and an approximation scheme
复制标题
小顶点连通性的打破二次时间和近似方案
DOI：
10.1145/3313276.3316394
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Sorrachai Yingchareonthawornchai
中科院分区：
文献类型：
--
作者：
Danupon Nanongkai;Thatchaphol Saranurak;Sorrachai Yingchareonthawornchai
点连通性是一个经典的被广泛研究的问题。给定一个整数k，它的目标是决定一个n-节点m-边图是否可以通过移除k个顶点而断开。虽然线性时间算法自1974年以来被假定[Aho，Hopcroft和Ullman]，尽管它的兄弟问题的边缘连接被解决了20多年前[Karger STOC'96]，到目前为止，没有顶点连接算法是快于O（n2）时间，即使k=4和m=O（n）。在最简单的情况下，其中m=O（n）和k=O（1），O（n2）的界限可以追溯到五十年前[Kleitman IEEE Trans. Circuit Theory'69]。对于更高的m，对于k≤ 3，O（m）时间是已知的[Tarjan FOCS'71; Hopcroft，Tarjan SICOMP'73]，第一个O（n2）时间是来自[Kanevsky，Ramachandran，FOCS'87]对于k=4和[Nagamochi，茨木，Yumica'92]对于k=O（1）。对于一般的k和m，最佳界是（min（kn 2，nω+nkω））[Henzinger，Rao，Gabow FOCS'96; Linial，Lovász，Wigderson FOCS'86]，其中隐藏多对数项，ω<2.38是矩阵乘法指数。本文提出了一个时间复杂度为n（m+ k ~ 7/3 n ~ 4/3）的随机Monte Carlo算法，其中k=O（n）.这给出了对于任何4≤ k ≤ o（n2/7）的第一次二次时间界（次二次时间指的是O（m）+o（n2）时间）。并改进了所有k≤ n 0.44的经典界。我们还提出了一个新的随机Monte Carlo（1+ 1）-近似算法，严格快于以前的Henzinger的2-近似算法[J.算法'97]和所有以前的精确算法。对于有向情况，情况也是一样的，其中我们的精确k（min{km 2/3 n，km 4/3}）-时间对于任何k = O（n）和（1+ n）-近似算法分别改进了小k和大k的经典界限。此外，我们的算法是有向图上的第一近似算法。我们的结果的关键是避免计算单源连接，这是需要由所有以前的精确算法，并不知道承认o（n2）的时间。相反，我们设计了第一个计算顶点连通性的局部算法;在不阅读整个图的情况下，我们的算法可以找到一个最大为k的分隔符，或者证明在给定的种子节点“附近”没有最大为k的分隔符。
Vertex connectivity a classic extensively-studied problem. Given an integer k, its goal is to decide if an n-node m-edge graph can be disconnected by removing k vertices. Although a linear-time algorithm was postulated since 1974 [Aho, Hopcroft and Ullman], and despite its sibling problem of edge connectivity being resolved over two decades ago [Karger STOC’96], so far no vertex connectivity algorithms are faster than O(n2) time even for k=4 and m=O(n). In the simplest case where m=O(n) and k=O(1), the O(n2) bound dates five decades back to [Kleitman IEEE Trans. Circuit Theory’69]. For higher m, O(m) time is known for k≤ 3 [Tarjan FOCS’71; Hopcroft, Tarjan SICOMP’73], the first O(n2) time is from [Kanevsky, Ramachandran, FOCS’87] for k=4 and from [Nagamochi, Ibaraki, Algorithmica’92] for k=O(1). For general k and m, the best bound is Õ(min(kn2, nω+nkω)) [Henzinger, Rao, Gabow FOCS’96; Linial, Lovász, Wigderson FOCS’86] where Õ hides polylogarithmic terms and ω<2.38 is the matrix multiplication exponent. In this paper, we present a randomized Monte Carlo algorithm with Õ(m+k7/3n4/3) time for any k=O(√n). This gives the first subquadratic time bound for any 4≤ k ≤ o(n2/7) (subquadratic time refers to O(m)+o(n2) time.) and improves all above classic bounds for all k≤ n0.44. We also present a new randomized Monte Carlo (1+є)-approximation algorithm that is strictly faster than the previous Henzinger’s 2-approximation algorithm [J. Algorithms’97] and all previous exact algorithms. The story is the same for the directed case, where our exact Õ( min{km2/3n, km4/3} )-time for any k = O(√n) and (1+є)-approximation algorithms improve classic bounds for small and large k, respectively. Additionally, our algorithm is the first approximation algorithm on directed graphs. The key to our results is to avoid computing single-source connectivity, which was needed by all previous exact algorithms and is not known to admit o(n2) time. Instead, we design the first local algorithm for computing vertex connectivity; without reading the whole graph, our algorithm can find a separator of size at most k or certify that there is no separator of size at most k “near” a given seed node.