A 5/4-Approximation for Subcubic 2EC Using Circulations

摘要

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 graphs, improving upon the current best approximation ratio of 5/4 + ε. 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 9/8 for all subcubic bridge-less graphs with up to 16 nodes. Moreover, we present a family of graphs that demonstrate the integrality gap 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.