An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs

Abstract

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\to {\mathbb{R}}^{+}$. In doing so, $d\ge 2$ is considered a constant. The previously best known approximation algorithm for this problem is the local improvement algorithm SquareImp proposed by Berman. It achieves a performance ratio of $\frac{d}{2}+\epsilon$ in time $\mathcal{O}(|V(G){|}^{d+1}\cdot (|V(G)|+|E(G)|)\cdot (d-1{)}^2\cdot {\left(\frac{d}{2\epsilon }+1\right)}^2)$ for any $\epsilon >0$, which has remained unimproved for the last twenty years. By considering a broader class of local improvements, we obtain an approximation ratio of $\frac{d}{2}-\frac{1}{63,700,992}+\epsilon$ for any $\epsilon >0$ at the cost of an additional factor of $\mathcal{O}(|V(G){|}^{(d-1{)}^2})$ in the running time. In particular, our result implies a polynomial time $\frac{d}{2}$-approximation algorithm. Furthermore, the well-known reduction from the weighted $k$-Set Packing Problem to the Maximum Weight Independent Set Problem in $k+1$-claw free graphs provides a $\frac{k+1}{2}-\frac{1}{63,700,992}+\epsilon$-approximation algorithm for the weighted $k$-Set Packing Problem for any $\epsilon >0$. This improves on the previously best known approximation guarantee of $\frac{k+1}{2}+\epsilon$ originating from the result of Berman.

full version of the paper "An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs" published in the proceedings of STACS 2021, 30 pages, 4 figures