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

作者：Boyd Sylvia^*; Fu Yao; Sun Yu

来源：Discrete Applied Mathematics, 2016, 209: 48-58.

DOI：10.1016/j.dam.2015.10.014

• Minimum 2-edge-connected subgraph problem
• Approximation algorithm
• Circulations
• Integrality gap
• Subcubic graphs

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.

• 出版日期2016-8-20