A simple approximation algorithm for WIS based on the approximability in k-partite graphs

In this note, simple approximation algorithms for the weighted independent set problem are presented with a performance ratio depending on ▵(G). These algorithms do not improve the best approximation algorithm known so far for this problem but they are of interest because of their simplicity. Precisely, we show how an optimum weighted independent set in bipartite graphs and a ρ‐approximation of WIS in k‐partite graphs respectively allows to obtain a 2/▵(G)‐approximation and a k/▵(G)ρ‐approximation in general graphs. Note that the ratio 2/▵(G) is the best bound known for the particular cases ▵(G) = 3 or ▵(G) = 4.