A Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphs
share
We propose a very simple and natural approximation algorithm for the problem of finding a 2-edge-connected spanning subgraph of minimum edge cost in a graph. The algorithm maintains a spanning forest starting with an empty edge set. In each iteration, a new edge incident to a leaf is selected in a natural greedy manner and added to the forest. If this produces a cycle, this cycle is contracted. This growing phase ends when the graph has been contracted into a single node and a subsequent cleanup step removes redundant edges in reverse order. We analyze the algorithm using the primal-dual method showing that its solution value is at most 3 times the optimum. This matches the ratio of existing primal-dual algorithms. The latter increase the connectivity in multiple phases, which is a main stumbling block of improving their approximation ratios further. We require only a single growing phase, which may open the door for further ratio improvements. Our algorithm is conceptually simpler than the known approximation algorithms. It works in O(nm) time without data structures more sophisticated than arrays, lists, and graphs, and without graph algorithms beyond depth-first search.
READ FULL TEXT