{"ID":6536184,"CreatedAt":"2026-07-14T01:21:01.169441415Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.10689","arxiv_id":"2607.10689","title":"Fully Dynamic Edge Connectivity in $\\tilde{O}(n^{12/13})$ Time","abstract":"In the (fully) dynamic edge connectivity problem, the goal is to maintain the edge connectivity $λ_G$ of an $n$-vertex graph $G$ that undergoes edge insertions and deletions. Our main result is a randomized algorithm for maintaining edge connectivity in dynamic simple graphs using worst-case update and query time $\\tilde{O}(n^{12/13})$, for all values of $λ_G$. This is the first algorithm that has $o(n)$ update and query time, as all existing algorithms achieve this only when $λ_G$ is below $n^{1/11}$ or above $n^{1/2}$ (up to polylogarithmic factors). We then use the tools developed for this purpose to design two additional algorithms. The first one is a deterministic algorithm for the exact same task, that uses $n^{1+o(1)}$ worst-case update and query time or $\\tilde{O}(n)$ amortized update and query time; this gives a polynomial improvement over existing deterministic algorithms. The second one is a deterministic algorithm for the same task but in dynamic unweighted multigraphs, that uses $\\tilde{O}(n^{3/2})$ worst-case update and query time.","short_abstract":"In the (fully) dynamic edge connectivity problem, the goal is to maintain the edge connectivity $λ_G$ of an $n$-vertex graph $G$ that undergoes edge insertions and deletions. Our main result is a randomized algorithm for maintaining edge connectivity in dynamic simple graphs using worst-case update and query time $\\til...","url_abs":"https://arxiv.org/abs/2607.10689","url_pdf":"https://arxiv.org/pdf/2607.10689v1","authors":"[\"Yotam Kenneth-Mordoch\",\"Robert Krauthgamer\"]","published":"2026-07-12T10:19:57Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}