Vertex subset of maximum size I was wondering if this problem has a name and/or it has been already studied.


  Problem: Given an undirected graph $G=(V,E)$, a function $f: V \to \mathbb N$, and a natural number $k$&nbsp;:
  Does there exist a subset $S\subseteq V$ with $|S| \geqslant k$, such that 
  $$ \forall v \in V \,:\, \biggl|\;\Bigr(N(v) \cup \{v\}\Bigr) \cap S\;\biggr| \;\leqslant\; f(v) \;?$$


Question.
Is this problem NP-complete? Are there good approximation algorithms?
I think a general polynomial time solution to this would be able to be used to solve k-SAT.

For each variable create two vertexes corresponding to true and false and connect them by an edge. Start by assigning k to to the number of variables (half the number of vertexes), and each of their f values to 1. Let not being in S mean true or false. Now we have a graph where each variable has to be either true or false.

For each OR operation on x variables create one vertex and connect it to the appropriate true/false vertexes.

For each OR operation create a large number Z of auxilary vertexes with an f value of 1, and connect each by an edge to the OR vertex. Increment k by Z for each OR operation. We can see this will force the OR operation vertex to not be a member of S, and all the auxilary vertexes to be in S.

Now assign the f value of each OR vertex to Z+x-1. Z of these will be taken by the auxilary vertexes.  The OR vertex is not in S, so this means at maximum x-1 of the connected variable vertexes can be in S, so at least one of the variable nodes connected to an OR vertex will have to not be in S.