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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Feb 12 at 4:55
  • $\begingroup$ You may suppose that there is no such paper for the specific problem, and ask here what you would like to get to know $\endgroup$
    – Smylic
    Mar 28 at 16:29
  • $\begingroup$ 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. $\endgroup$
    – Smylic
    Mar 28 at 16:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.