Towards Subpolynomial-time Fully Dynamic Minimum Cut

In the age of big data, traditional static graph algorithms struggle to keep up with the dynamic nature of real-world networks. Dynamic graph algorithms become increasingly important because they allow for the continuous updating and querying of graphs as new data comes in, enabling real-time insights and decision-making. This capability is crucial for real-world applications where timely information can significantly impact outcomes. In this dissertation, we present fully dynamic algorithms for the graph c-edge connectivity problem. We begin by discussing the history of fully dynamic edge connectivity research and the improvements made in the last decade that our research builds upon. We then present a deterministic fully dynamic data structure that can answer c-edge connectivity queries. Given a dynamic graph G with n vertices that undergoes edge insertion and deletion updates, our data structure is able to answer c-edge connectivity queries on a pair of vertices in no(1) time worst-case update and query time, for any c = logo(1) n. This result was published in FOCS 2021. Next, building upon our previously described c-edge connectivity data structure, we develop an extended dynamic data structure that deterministically maintains a minimum cut of size at most c, where c = logo(1) n. This new data structure achieves no(1) worst-case time complexity for both updates and queries. Our work on this topic was presented at SODA 2024. Finally, we discuss the barriers and attempts to remove the c = logo(1) n qualifier.