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 $(\frac 5 4 + \varepsilon)$-approximation for the problem for an arbitrarily small $\varepsilon>0$, improving the previous best approximation ratio of $\frac{13}{10}+\varepsilon$. 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.

翻译：我们研究双边连通生成子图（2-ECSS）问题：给定图$G$，计算$G$的一个连通子图$H$，使得$H$是生成子图（即$V(H) = V(G)$）且$H$是双边连通的（即删除任意单条边后$H$仍保持连通），同时要求$H$的边数最小（若这样的$H$存在）。已知2-ECSS问题是NP难问题。本文提出了一种多项式时间的$(\frac{5}{4} + \varepsilon)$近似算法（其中$\varepsilon>0$为任意小常数），将先前最佳近似比$\frac{13}{10}+\varepsilon$进一步提升。我们的改进基于两项核心创新：首先，将一般图上的问题归约到具有高顶点连通度的结构化图上求解。这种高顶点连通度保证了对于顶点集的任意二分划（每部分至少包含10个顶点），都存在跨越该二分划的4-匹配。其次，我们在后续粘合步骤中利用该性质，将孤立的双边连通分量进行合并且避免添加过多边。借助4-匹配性质，我们可以反复将巨型分量（包含至少10个顶点）与其他分量粘合。这一过程让人联想到Pac-Man游戏：一个Pac-Man（巨型分量）在迷宫中移动时吞噬所有小点（其他分量）。相较于先前需要冗长繁琐案例分析的最佳近似算法，这两项创新使得粘合步骤的算法设计与分析显著简化。