A 5/4-approximation for subcubic 2EC using circulations and obliged edges

In this paper we study the NP-hard problem of finding a minimum size 2-edge-connected spanning subgraph (henceforth 2EC) in cubic and subcubic multigraphs. We present a new 5/4-approximation algorithm for 2EC for subcubic bridgeless multigraphs, improving upon the current best approximation ratio of 5/4 + epsilon. Our algorithm involves an elegant new method based on circulations which we feel has potential to be more broadly applied. We also study the closely related integrality gap problem, i.e. the worst case ratio between the integer linear program for 2EC and its linear programming relaxation, both theoretically and computationally. We show this gap is at most 5/4 for subcubic bridgeless multigraphs, and is at most 9/8 for all subcubic bridgeless graphs with up to 16 nodes. Moreover, we present a family of graphs that demonstrate the integrality gap for 2EC is at least 8/7, even when restricted to subcubic bridgeless graphs. This represents an improvement over the previous best known bound of 9/8. (C) 2015 Elsevier B.V. All rights reserved.