Title: A Better-Than-$5/4$-Approximation for Two-Edge Connectivity Show Chinese title

Title: 一种优于$5/4$的二边连通性近似方法

Abstract: The 2-Edge-Connected Spanning Subgraph Problem (2ECSS) is a fundamental problem in survivable network design. Given an undirected $2$-edge-connected graph, the goal is to find a $2$-edge-connected spanning subgraph with the minimum number of edges; a graph is 2-edge-connected if it is connected after the removal of any single edge. 2ECSS is APX-hard and has been extensively studied in the context of approximation algorithms. Very recently, Bosch-Calvo, Garg, Grandoni, Hommelsheim, Jabal Ameli, and Lindermayr showed the currently best-known approximation ratio of $\frac{5}{4}$ [STOC 2025]. This factor is tight for many of their techniques and arguments, and it was not clear whether $\frac{5}{4}$ can be improved. We break this natural barrier and present a $(\frac{5}{4} - \eta)$-approximation algorithm, for some constant $\eta \geq 10^{-6}$. On a high level, we follow the approach of previous works: take a triangle-free $2$-edge cover and transform it into a 2-edge-connected spanning subgraph by adding only a few additional edges. For $\geq \frac{5}{4}$-approximations, one can heavily exploit that a $4$-cycle in the 2-edge cover can ``buy'' one additional edge. This enables simple and nice techniques, but immediately fails for our improved approximation ratio. To overcome this, we design two complementary algorithms that perform well for different scenarios: one for few $4$-cycles and one for many $4$-cycles. Besides this, there appear more obstructions when breaching $\frac54$, which we surpass via new techniques such as colorful bridge covering, rich vertices, and branching gluing paths. Show Chinese abstract

Abstract: 2-边连通生成子图问题（2ECSS）是容错网络设计中的一个基本问题。 给定一个无向$2$-边连通图，目标是找到一个边数最少的$2$-边连通生成子图；如果在删除任意一条边后图仍然连通，则该图是2-边连通的。 2ECSS是APX难问题，并且在近似算法的背景下被广泛研究。 最近，Bosch-Calvo、Garg、Grandoni、Hommelsheim、Jabal Ameli和Lindermayr展示了目前最好的近似比为$\frac{5}{4}$[STOC 2025]。 这个因子对于他们许多技术与论证来说是紧的，而且不清楚是否可以改进$\frac{5}{4}$。 我们打破了这一自然障碍，提出了一种$(\frac{5}{4} - \eta)$近似算法，其中$\eta \geq 10^{-6}$是某个常数。 从高层次来看，我们遵循了之前工作的思路：取一个不含三角形的$2$-边覆盖，并通过仅添加少量额外边将其转换为2-边连通的生成子图。 对于$\geq \frac{5}{4}$-近似，可以充分利用在2边覆盖中的$4$-环可以“购买”一个额外的边这一特性。 这使得简单且优美的技术成为可能，但立即在我们改进的近似比下失效。 为了克服这一点，我们设计了两个互补的算法，分别在不同场景下表现良好：一个用于少量$4$-环，另一个用于大量$4$-环。 除此之外，在突破$\frac54$时会出现更多的障碍，我们通过新的技术如彩色桥覆盖、丰富顶点和分支粘合路径来克服这些障碍。