论文标题
提高了双边连接性的近似值
Improved Approximation for Two-Edge-Connectivity
论文作者
论文摘要
可生存的网络设计的基本目标是构建低成本网络，尽管失败或删除了一些节点或边缘，该网络仍可以保持足够的连接水平。该领域中最基本的问题之一是$ 2 $ - 与跨性别子图问题（2-ECSS）：给定无向图$ g $，找到一个$ 2 $ - 边缘连接的跨度子级$ h $ g $ $ g $的$ g $具有最低边缘数量（尤其是在$ h $中，$ h $在一个任意边缘的拆卸后仍保持连接）。 2-ECS是NP固定的，此问题的最著名（多项式时间）近似因素为$ 4/3 $。有趣的是，[hunkenschr {Ö} der，vempala和vetta '00，'19]和[seb {Ö}和Vygen，'14]通过[hunkenschr {Ö} der，vempala和vetta '00，'00，'14]实现了这一因素。在本文中，我们提出了一个改进的$ \ frac {118} {89}+ε<1.326 $ <1.326 $近似。 我们方法中的关键要素（这也可能在以后的工作中有所帮助）是将特殊类型的结构化图的减少：我们的还原可保留高达$ 6/5 $的近似因素。 While reducing to 2-vertex-connected graphs is trivial (and heavily used in prior work), our structured graphs are "almost" 3-vertex-connected: more precisely, given any 2-vertex-cut $\{u,v\}$ of a structured graph $G=(V,E)$, $G[V\setminus \{u,v\}]$ has exactly 2连接的组件，其中一个包含一个恰好的$ 2 $ in $ g $的节点。
The basic goal of survivable network design is to construct low-cost networks which preserve a sufficient level of connectivity despite the failure or removal of a few nodes or edges. One of the most basic problems in this area is the $2$-Edge-Connected Spanning Subgraph problem (2-ECSS): given an undirected graph $G$, find a $2$-edge-connected spanning subgraph $H$ of $G$ with the minimum number of edges (in particular, $H$ remains connected after the removal of one arbitrary edge). 2-ECSS is NP-hard and the best-known (polynomial-time) approximation factor for this problem is $4/3$. Interestingly, this factor was achieved with drastically different techniques by [Hunkenschr{ö}der, Vempala and Vetta '00,'19] and [Seb{ö} and Vygen, '14]. In this paper we present an improved $\frac{118}{89}+ε<1.326$ approximation for 2-ECSS. The key ingredient in our approach (which might also be helpful in future work) is a reduction to a special type of structured graphs: our reduction preserves approximation factors up to $6/5$. While reducing to 2-vertex-connected graphs is trivial (and heavily used in prior work), our structured graphs are "almost" 3-vertex-connected: more precisely, given any 2-vertex-cut $\{u,v\}$ of a structured graph $G=(V,E)$, $G[V\setminus \{u,v\}]$ has exactly 2 connected components, one of which contains exactly one node of degree $2$ in $G$.
