Vertex Connectivity via Local Computation: Breaking Quadratic Time, Poly-logarithmic Max-flows, and Derandomization

Thumbnail Image
Files
isbn9789526413402.pdf (1.78 MB)
Journal Title
Journal ISSN
Volume Title
School of Science | Doctoral thesis (article-based) | Defence date: 2023-07-25
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Author
Date
2023
Department
Tietotekniikan laitos
Department of Computer Science
Major/Subject
Mcode
Degree programme
Language
en
Pages
82 + app. 98
Series
Aalto University publication series DOCTORAL THESES, 104/2023
Abstract
Vertex connectivity is a classic graph-theoretic notion, that roughly measures the robustness of a network against vertex failure. Vertex connectivity k of an n-vertex m-edge graph is the minimum number of vertices to be removed to disconnect the graph. A major open problem asked almost 50 years ago is whether or not vertex connectivity can be computed in linear time [Aho, Hopcroft, and Ullman 1974, Problem 5.30].  Vertex connectivity can be solved in linear time when k =1 and k = 2 using a depth-first search tree [Tarjan'72] and a basic data structure called SPQR tree [Hopcroft and Tarjan'73], respectively. When k >2, it remains an open problem. For general connectivity, the fastest known algorithms take time O(mn) [Henziner, Rao and Gabow FOCS'96] and O(T(n)+nT(k)) [Linial, Lovász, Wigderson FOCS'86] where T(n) is the time to multiply two n-by-n matrices. Even for the special case when k = O(1) and m = O(n), both algorithms run at least n2 time. In this case, the quadratic time barrier was known 50 years ago [Kleitman'69]. In this thesis, we break the long-standing quadratic time barrier and affirmatively resolve the open problem by Aho, Hopcroft, and Ullman (up to a sub-polynomial factor). We show the following results:1. An O(m+nk3)-time randomized algorithm. The algorithm takes O(m+n) time whenever k is sufficiently small. Here, the poly-logarithmic factor in the running time is omitted.2. A randomized reduction to poly-logarithmic number of many calls to a max-flow algorithm. Thus, vertex connectivity can be solved in almost linear time by using the almost linear time max-flow algorithm [Chen, Kyng, Liu, Peng, Probst and Sachdeva FOCS'22]. 3. An almost linear time deterministic algorithm whenever k is sufficiently small. To achieve these results, we introduce local computation frameworks that could be potentially extended beyond vertex connectivity. We show that fast local cut computation implies fast vertex connectivity and develop fast local cut detection algorithms that lead to the O(m+nk3)-time vertex connectivity algorithm. By making a connection to the theory of kernelization, we solve vertex connectivity in poly-logarithmic max-flows. Finally, we use vertex expanders and vertex cut sparsifiers to derandomize the vertex connectivity algorithm for small vertex connectivity.  
Description
Supervising professor
Chalermsook, Parinya, Asst. Prof., Aalto University, Department of Computer Science, Finland
Thesis advisor
Nanongkai, Danupon, Prof., Max Planck Institute for Informatics and Saarland University, Germany
Keywords
algorithmic graph theory, sublinear algorithms, kernelization, property testing
Other note
Parts
  • [Publication 1]: Danupon Nanongkai, Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai. Breaking Quadratic Time For Small Vertex Connectivity and Approximation Scheme. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019,Pages 241–252, June 2019.
    Full text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto-202001021403
    DOI: 10.1145/3313276.3316394 View at publisher
  • [Publication 2]: Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurakand Sorrachai Yingchareonthawornchai. Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithm. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Pages 2046-2065, January2020.
    DOI: 10.1137/1.9781611975994.126 View at publisher
  • [Publication 3]: Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai. Vertex Connectivity in Poly-logarithmic Max-flows. In 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, Pages 317-329, June 2021.
    Full text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto-202107017890
    DOI: 10.1145/3406325.3451088 View at publisher
  • [Publication 4]: Thatchaphol Saranurak and Sorrachai Yingchareonthawornchai. Deterministic Small Vertex Connectivity in Almost Linear Time. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Pages 789-800, October 2022.
    Full text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto-202301181336
    DOI: 10.1109/FOCS54457.2022.00080 View at publisher
  • [Publication 5]: Max Franck and Sorrachai Yingchareonthawornchai. Engineering Nearly Linear-time Algorithms for Small Vertex Connectivity. ACM Journal of Experimental Algorithmics, Volume 27, Article No.: 4.4, Pages 1 - 29, December 2022.
    Full text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto-202107017827
    DOI: 10.4230/LIPIcs.SEA.2021.1 View at publisher
Citation
Permanent link to this item
https://urn.fi/URN:ISBN:978-952-64-1340-2
Collections
[diss] Perustieteiden korkeakoulu / SCI