On maximal k-edge-connected subgraphs of undirected graphs

We provide the following new results on maximal k-edge-connected subgraphs of undirected graphs. (1) A general framework for maintaining the maximal k-edge-connected subgraphs upon insertions of edges or vertices, by successively partitioning the graph into its k-edge-connected components. This defines a decomposition tree, which can be maintained by using algorithms for the incremental maintenance of the k-edge-connected components as black boxes at every level of the tree. As a concrete application of this framework, we provide two algorithms for the incremental maintenance of the maximal 3-edge-connected subgraphs. These algorithms allow for vertex and edge insertions, interspersed with queries asking whether two vertices belong to the same maximal 3-edge-connected subgraph, and there is a trade-off between their time-and space-complexity. Specifically, the first algorithm has O (m alpha (m, n) + n2 log2 n) total running time and uses O(n) space, where m is the number of edge insertions and queries, and n is the total number of vertices inserted starting from an empty graph. The second algorithm performs the same operations in faster O (m alpha (m, n) +n2 alpha (n, n)) time in total, using O(n2) space. (2) We provide efficient constructions of (almost) sparse spanning subgraphs that have the same maximal k-edge-connected subgraphs as the original graph. We refer to such subgraphs as k-certificates. We use those certificates to speed up the computation of the maximal k-edge-connected subgraphs in the static and the fully-dynamic setting. (3) Finally, we give a simple reduction for computing the maximal k-edge-connected subgraphs to a fully dynamic mincut algorithm. (c) 2026 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).