2022/11/12 by Georgiadis, Loukas, Italiano, Giuseppe F., Kosinas, Evangelos +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2211.06521
We show how to find and efficiently maintain maximal k-edge-connected subgraphs in undirected graphs. In particular, we provide the following results. (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. (2) As an 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. The first algorithm has O(mα(m,n) + n2log2 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. The second algorithm performs the same operations in faster O(mα(m,n) + n2α(n,n)) time in total, using O(n2) space. (3) We provide efficient constructions of sparse subgraphs that have the same maximal k-edge-connected subgraphs as the original graph. These are useful in speeding up computations involving the maximal k-edge-connected subgraphs in dense undirected graphs. (4) We give two deterministic algorithms for computing the maximal k-edge-connected subgraphs in undirected graphs, with running times O(m+kO(1)n√(n)polylog(n)) and O(m+kO(k)n√(n)logn), respectively. (5) A fully dynamic algorithm for maintaining information about the maximal k-edge-connected subgraphs for fixed k. Our update bounds are O(n√(n)logn) worst-case time, and we achieve constant time for maximal k-edge-connected subgraph queries.