Breaking quadratic time for small vertex connectivity and an approximation scheme
Loading...
Access rights
openAccess
acceptedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
12
Series
STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 241-252, Proceedings of the Annual ACM Symposium on Theory of Computing
Abstract
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 all previous exact bounds. 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.Description
| openaire: EC/H2020/715672/EU//DisDyn
Other note
Citation
Nanongkai, D, Saranurak, T & Yingchareonthawornchai, S 2019, Breaking quadratic time for small vertex connectivity and an approximation scheme. in M Charikar & E Cohen (eds), STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, ACM, pp. 241-252, ACM Symposium on Theory of Computing, Phoenix, Arizona, United States, 23/06/2019. https://doi.org/10.1145/3313276.3316394