Breaking quadratic time for small vertex connectivity and an approximation scheme
dc.contributor | Aalto-yliopisto | fi |
dc.contributor | Aalto University | en |
dc.contributor.author | Nanongkai, Danupon | en_US |
dc.contributor.author | Saranurak, Thatchaphol | en_US |
dc.contributor.author | Yingchareonthawornchai, Sorrachai | en_US |
dc.contributor.department | Department of Computer Science | en |
dc.contributor.editor | Charikar, Moses | en_US |
dc.contributor.editor | Cohen, Edith | en_US |
dc.contributor.groupauthor | Professorship Chalermsook Parinya | en |
dc.contributor.organization | KTH Royal Institute of Technology | en_US |
dc.contributor.organization | University of Chicago | en_US |
dc.date.accessioned | 2020-01-02T14:13:02Z | |
dc.date.available | 2020-01-02T14:13:02Z | |
dc.date.issued | 2019-06-23 | en_US |
dc.description | | openaire: EC/H2020/715672/EU//DisDyn | |
dc.description.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. | en |
dc.description.version | Peer reviewed | en |
dc.format.extent | 12 | |
dc.format.extent | 241-252 | |
dc.format.mimetype | application/pdf | en_US |
dc.identifier.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 | en |
dc.identifier.doi | 10.1145/3313276.3316394 | en_US |
dc.identifier.isbn | 9781450367059 | |
dc.identifier.issn | 0737-8017 | |
dc.identifier.other | PURE UUID: f06841db-3a10-469e-813d-34abfabad2f6 | en_US |
dc.identifier.other | PURE ITEMURL: https://research.aalto.fi/en/publications/f06841db-3a10-469e-813d-34abfabad2f6 | en_US |
dc.identifier.other | PURE LINK: http://www.scopus.com/inward/record.url?scp=85068776840&partnerID=8YFLogxK | en_US |
dc.identifier.other | PURE FILEURL: https://research.aalto.fi/files/39496721/SCI_Nanongkai_et.al_Breaking_Quadratic.main_vertex_conn.pdf | en_US |
dc.identifier.uri | https://aaltodoc.aalto.fi/handle/123456789/42292 | |
dc.identifier.urn | URN:NBN:fi:aalto-202001021403 | |
dc.language.iso | en | en |
dc.relation | info:eu-repo/grantAgreement/EC/H2020/715672/EU//DisDyn | en_US |
dc.relation.ispartof | ACM Symposium on Theory of Computing | en |
dc.relation.ispartofseries | STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | en |
dc.relation.ispartofseries | Proceedings of the Annual ACM Symposium on Theory of Computing | en |
dc.rights | openAccess | en |
dc.subject.keyword | Graph algorithms | en_US |
dc.subject.keyword | Local flow algorithms | en_US |
dc.subject.keyword | Vertex connectivity | en_US |
dc.title | Breaking quadratic time for small vertex connectivity and an approximation scheme | en |
dc.type | A4 Artikkeli konferenssijulkaisussa | fi |
dc.type.version | acceptedVersion |