# Find an independent set in which the cumulative sum of weights is maximized

I have a weighted undirected graph G=(V,E,W), I want to find an independent set S of V, such that if we sort the vertices of S in increasing order of their weights, the cumulative sum of the weights is maximized. In other words, if we suppose without loose of generality that $$S={v_1,...,v_h}$$ are the vertices of $$S$$ sorted in increasing order of their weights, then we want to maximize $$\sum_{i=1}^{h} \sum_{j=1}^{i}w_j$$, where $$w_j$$ is the weight of vertex $$v_j$$.

This problem is NP-hard since it can be reduced to the maximum independent set problem when all the weights are equal, but I can't find in the literature a paper dealing with this problem, can you please share any work on this problem or related problems.

For instance if the weights of my independent set are {3,6} than the cumulative sum is 3+(3+6)=12, and if the weights are {1,1,2,3} than my cumulative sum is: 1+(1+1)+(1+1+2)+(1+1+2+3)=14. So an independent set of maximum weight is not necessary yielding the maximum cumulative sum of weights.

• Cross-posted: stackoverflow.com/q/77931790/781723. Please pick one site where you want this to appear. Please do not post the same question on multiple sites.
– D.W.
Feb 12 at 4:55
• You may suppose that there is no such paper for the specific problem, and ask here what you would like to get to know Mar 28 at 16:29
• Also this problem is $\mathrm{NP}$-hard because maximum independent set problem can be reduced to this one, not because of reduction in the opposite direction. Mar 28 at 16:30