2022/11/03 by Kashaev, Danish, Schäfer, Guido · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2211.01699
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 G := G /S and satisfies ρ∈ [2,∞]. If S is an arbitrary set, we prove a tight approximation ratio of (1+1/ρ) (1 - α) + 2 α, where α∈ [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 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.