摘要 : We consider the polynomial approximation behavior of the problem of finding, in a graph with weighted vertices, a maximal independent set minimizing the sum of the weights. In the spirit of a work of Halldorson dealing with the un... 展开 We consider the polynomial approximation behavior of the problem of finding, in a graph with weighted vertices, a maximal independent set minimizing the sum of the weights. In the spirit of a work of Halldorson dealing with the unweighted case, we extend it and perform approximation hardness results by using a reduction from the minimum coloring problem. In particular, a consequence of our main result is that there does not exist any polynomial time algorithm approximating this problem within a ratio independent of the weights, unless P identical with NP. We bring also to the fore a very simple ratio rho guaranteed by every algorithm while no polynomial time algorithm can guarantee the ratio (1 - epsilon ) rho . The known hardness results for the unweighted case can be deduced. We finally discuss approximation results for both weighted and unweighted cases: we perform an approximation ratio that is valid for any algorithm for the former and propose an analysis of a greedy algorithm for the latter. 收起