A note on the approximation of a minimum-weight maximal independent set

We consider the polynomial approximation behavior of the problem of finding , in a graph with weighted vertices, a maximal independent set minimizing t he sum of the weights. In the spirit of a work of Halldorson dealing with t he unweighted case, we extend it and perform approximation hardness results by using a reduction from the minimum coloring problem. In particular, a c onsequence of our main result is that there does not exist any polynomial t ime algorithm approximating this problem within a ratio independent of the weights, unless P = NP. We bring also to the fore a very simple ratio rho g uaranteed by every algorithm while no polynomial time algorithm can guarant ee the ratio (1 - epsilon)rho. The known hardness results for the unweighte d case can be deduced. We finally discuss approximation results for both we ighted and unweighted cases: we perform an approximation ratio that is vali d for any algorithm for the former and propose an analysis of a greedy algo rithm for the latter.