论文标题
圆形和两次化以进行顶点盖近似
Round and Bipartize for Vertex Cover Approximation
论文作者
论文摘要
顶点覆盖问题是一个基本且经过广泛研究的组合优化问题。众所周知，其标准线性编程松弛是两部分图的组成部分，而对于一般图形来说，这是一半综合图。结果，基于此松弛的天然圆形算法计算了两部分图的最佳解决方案，并为一般图的$ 2 $ approximation计算。这就提出了一个问题，即是否可以以最差的方式插入标准线性编程放松的圆形曲线，这取决于图与两分的距离。在本文中，我们考虑了一种简单的圆形算法，该算法利用了诱导的两分子图的知识来提高近似值。等效地，我们假设我们与一对$（g，s）$一起工作，由具有奇数循环横向的图组成。 如果$ s $是稳定的集合，我们证明$ 1 + 1 /ρ$的紧密近似值，其中$2ρ-1$表示合同图形的奇数（即，最短奇数周期的长度）$ \ tilde $ \ tilde {g}：= g /s $和满足$ρph.2，in [2，\ infty] $。如果$ s $是任意集，我们证明$ \左（1 + 1/ρ\右）的紧密近似值（1-α） +2α$，其中$α\ in [0,1] $是一个自然参数，测量了集合$ s $的质量。用于证明紧密改善的近似比的技术依赖于合同图$ \ tilde {g} $的结构分析。通过构造与所获得的上限匹配的重量功能的类别显示，显示了紧密度。作为结构分析的副产品，我们在整数间隙和3色图的分数色差上获得了改善的紧密界限。我们还讨论了算法应用程序，以找到良好的奇数循环横向并显示出分析的最佳性。
The vertex cover problem is a fundamental and widely studied combinatorial optimization problem. It is known that its standard linear programming relaxation is integral for bipartite graphs and half-integral for general graphs. As a consequence, the natural rounding algorithm based on this relaxation computes an optimal solution for bipartite graphs and a $2$-approximation for general graphs. This raises the question of whether one can interpolate the rounding curve of the standard linear programming relaxation in a beyond the worst-case manner, depending on how close the graph is to being bipartite. In this paper, we consider a simple rounding algorithm that exploits the knowledge of an induced bipartite subgraph to attain improved approximation ratios. Equivalently, we suppose that we work with a pair $(G, S)$, consisting of a graph with an odd cycle transversal. If $S$ is a stable set, we prove a tight approximation ratio of $1 + 1/ρ$, where $2ρ-1$ denotes the odd girth (i.e., length of the shortest odd cycle) of the contracted graph $\tilde{G} := G /S$ and satisfies $ρ\in [2,\infty]$. If $S$ is an arbitrary set, we prove a tight approximation ratio of $\left(1+1/ρ\right) (1 - α) + 2 α$, where $α\in [0,1]$ is a natural parameter measuring the quality of the set $S$. The technique used to prove tight improved approximation ratios relies on a structural analysis of the contracted graph $\tilde{G}$. Tightness is shown by constructing classes of weight functions matching the obtained upper bounds. As a byproduct of the structural analysis, we obtain improved tight bounds on the integrality gap and the fractional chromatic number of 3-colorable graphs. We also discuss algorithmic applications in order to find good odd cycle transversals and show optimality of the analysis.
