Computing the 5-Edge-Connected Components in Linear Time

We provide a deterministic algorithm for computing the 5-edge-connected components of an undirected multigraph in linear time. There were probably good indications that this computation can be performed in linear time, but no such algorithm was actually known prior to this work. Thus, our paper answers a theoretical question, and sheds light on the possibility that a solution may exist for general k. Furthermore, although the algorithm that we provide is quite extensive and broken up into several pieces, it can have an almost-linear time implementation with the use of elementary data structures. A key component in our algorithm is an oracle for answering connectivity queries for pairs of vertices in the presence of at most four edge-failures. Specifically, the oracle has size O(n), it can be constructed in linear time, and it answers connectivity queries in the presence of at most four edge-failures in O(1) time, where n denotes the number of vertices of the graph. We note that this is a result of independent interest.

Our paper can be considered as a follow-up of recent work on computing the 4-edge-connected components in linear time. Specifically, we follow a DFS-based approach in order to compute a collection of 4-edge cuts, that is rich enough in properties for our purposes. Furthermore, we expand the toolkit of DFS-based concepts, and demonstrate its general usefulness. In particular, our oracle for connectivity queries is also based on them. However, in dealing with the computation of the 5-edge-connected components, we are faced with unique challenges that do not appear when dealing with lower connectivity. The problem is that the 4-edge cuts in 3-edge-connected graphs are entangled in various complicated ways, that make it difficult to organize them in a compact way. Here we provide a novel analysis of those cuts, that reveals the existence of various interesting structures. These can be exploited so that we can disentangle and collect only those cuts that are essential in computing the 5-edge-connected components. This analysis may provide a clue for a general solution for the k-edge-connected components, or other related graph connectivity problems.