Passing the Limits of Pure Local Search for the Maximum Weight Independent Set Problem in d-Claw Free Graphs
share
In this paper, we consider the task of computing an independent set of maximum weight in a given d-claw free graph G=(V,E) equipped with a positive weight function w:V→ℝ_>0. Recently, Neuwohner has shown how to obtain approximation ratios of d-1+ϵ_d/2 in quasi-polynomial time, where 0≤ϵ_d≤ 1 and lim_d→∞ϵ_d = 0. For the special case of the d-1-Set Packing Problem, she showed how to get down to a polynomial running time. On the other hand, she provided examples showing that no local improvement algorithm considering local improvements of logarithmic size can yield an approximation guarantee better than d-1/2. However, it turns out that if one considers local improvements that arise by dropping vertex weights and running an algorithm devised for the unweighted setting on certain sub-instances of the given one, one can get beyond the d-1/2-threshold and obtain approximation guarantees of d/2-Ω(d) in quasi-polynomial time. For d-1-Set Packing instances, we can guarantee a polynomial running time. We also conduct a more general investigation of the relation between approximation guarantees for the unweighted and weighted variants of both the Maximum Weight Independent Set Problem in d-claw free graphs and the d-1-Set Packing problem. In doing so, we can show that for any constant σ > 0, there exists a constant τ > 0 such that a (quasi-)polynomial time 1+τ· (d-2)-approximation for the unweighted d-1-Set Packing Problem (the Maximum Cardinality Independent Set problem in d-claw free graphs) implies a (quasi-)-polynomial time 1+σ· (d-2)-approximation for the weighted d-1-Set Packing Problem (the Maximum Weight Independent Set problem in d-claw free graphs).
READ FULL TEXT