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.