Two-Edge Connectivity via Pac-Man Gluing.

Abstract: 

We study the 2-edge-connected spanning subgraph (2-ECSS) problem: Given a graph G, compute a connected subgraph H of G with the minimum number of edges such that H is spanning, i.e., V(H) = V(G), and H is 2-edge-connected, i.e., H remains connected upon the deletion of any single edge, if such an H exists. The 2-ECSS problem is known to be NP-hard. In this work, we provide a polynomial-time (5/4 + epsilon)-approximation for the problem for an arbitrarily small epsilon>0, improving the previous best approximation ratio of 13/10 + epsilon.

Our improvement is based on two main innovations: First, we reduce solving the problem on general graphs to solving it on structured graphs with high vertex connectivity. This high vertex connectivity ensures the existence of a 4-matching across any bipartition of the vertex set with at least 10 vertices in each part. Second, we exploit this property in a later gluing step, where isolated 2-edge connected components need to be merged without adding too many edges. Using the 4-matching property, we can repeatedly glue a huge component (containing at least 10 vertices) to other components. This step is reminiscent of the Pac-Man game, where a Pac-Man (a huge component) consumes all the dots (other components) as it moves through a maze. These two innovations lead to a significantly simpler algorithm and analysis for the gluing step compared to the previous best approximation algorithm, which required a long and tedious case analysis.

Posted on Mar 17, 2025 in ACGO, Seminars