Vertex Connectivity via Local Computation: Breaking Quadratic Time, Polylogarithmic Maxflows, and Derandomization
Loading...
Journal Title
Journal ISSN
Volume Title
School of Science 
Doctoral thesis (articlebased)
 Defence date: 20230725
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.
Date
2023
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 graphtheoretic notion, that roughly measures the robustness of a network against vertex failure. Vertex connectivity k of an nvertex medge 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 depthfirst 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 nbyn 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 longstanding quadratic time barrier and affirmatively resolve the open problem by Aho, Hopcroft, and Ullman (up to a subpolynomial 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 polylogarithmic factor in the running time is omitted.2. A randomized reduction to polylogarithmic number of many calls to a maxflow algorithm. Thus, vertex connectivity can be solved in almost linear time by using the almost linear time maxflow 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 polylogarithmic maxflows. 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, FinlandThesis advisor
Nanongkai, Danupon, Prof., Max Planck Institute for Informatics and Saarland University, GermanyKeywords
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:aalto202001021403DOI: 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 NearLinear Time and Queries via Fast Local Cut Algorithm. In Proceedings of the 2020 ACMSIAM Symposium on Discrete Algorithms, SODA 2020, Pages 20462065, 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 Polylogarithmic Maxflows. In 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, Pages 317329, June 2021.
Full text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto202107017890DOI: 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 789800, October 2022.
Full text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto202301181336DOI: 10.1109/FOCS54457.2022.00080 View at publisher

[Publication 5]: Max Franck and Sorrachai Yingchareonthawornchai. Engineering Nearly Lineartime 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:aalto202107017827DOI: 10.4230/LIPIcs.SEA.2021.1 View at publisher