Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Breaking quadratic time for small vertex connectivity and an approximation scheme
KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
2019 (English)In: STOC 2019 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery (ACM), 2019, p. 241-252Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2019. p. 241-252
Keywords [en]
Graph algorithms, Local flow algorithms, Vertex connectivity
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-262618DOI: 10.1145/3313276.3316394Scopus ID: 2-s2.0-85068776840ISBN: 9781450367059 (print)OAI: oai:DiVA.org:kth-262618DiVA, id: diva2:1362732
Conference
51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019; Phoenix; United States; 23 June 2019 through 26 June 2019
Note

QC 20191021

Available from: 2019-10-21 Created: 2019-10-21 Last updated: 2019-10-21Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Nanongkai, Danupon
By organisation
Theoretical Computer Science, TCS
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 9 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf