# graphs – Maximal independent set, with non-additive weights

Consider the following variant of the problem of finding the maximal weighted independent set in a vertex-weighted graph $$G=G(V,E)$$. Weights $$w_v$$ for $$vin V$$ need not be positive reals; say they lie in $$mathbb{R}_{ge0}^n$$. Say we are given a function $$f:mathbb{R}_{ge0}^nlongrightarrowmathbb{R}$$ (assume it’s efficiently computable, for instance, $$f(x_1,dots,x_n)=x_1cdots x_n$$). For an independent set $$Ssubset V$$, call $$f(S)=fleft(sumlimits_{sin S}w_sright)$$. We seek $$max f(S)$$ or $$mathrm{argmax}f(S)$$ (both taken over independent sets $$S$$). If $$n=1$$ and $$f$$ is the identity, then obviously if also $$w_vequiv1$$ then this is exactly the maximal independent set problem, and removing that last condition, this generalizes to the maximal weighted independent set problem (which I think also has been studied?). What I’m curious about is: is there anything known about more-efficient-than-brute-force methods for solving any other special cases? Another special case of particular interest is $$f(x_1,dots,x_n)=begin{cases}x_1+cdots+x_n & forall i:x_ineq0\0&exists i:x_i=0,end{cases}$$ and more generally any special case that returns 0 iff some component is 0. Thanks in advance.