To show that the problem is NP complete

Question

A decision problem: For a given graph G and numbers 'a','b' it is required to be answered whether there is a set of 'a' vertices which have a cumulative neighborhood of size at least 'b'. How do we show that this problem is NPC?

Answer 1

I assume that you're looking for a set $S$ with size $a = |S|$ and you're taking the union of the neighbors, so $b = \cup_{v\in S} n(v)$ (where $n(v)$ is the set of all vertices that share a neighbor with $b$).*

Then we can reduce from set cover with $b \gets m + k(n+1)$ and $a \gets k$. We create a vertex for each of the $m$ sets in the Set Cover instance, and we also create a vertex for each of the $n$ items which may be contained in a set. We create an edge between a set and an item iff the set contains that item.

For each of the $n$ "item vertices" created above, we create $n+1$ more vertices, and add edges between them. (This means it's never good to select one of the "set" vertices.)

Then there is a set cover of size $k$ if and only if there are $k$ vertices with total neighborhood size $m + k(n+1)$.

*A note on problem variants: if you are adding the neighborhood sizes (rather than taking the union as I assumed), just take the vertices with largest neighborhood greedily and the problem is trivial. Whether or not "selected" vertices count towards neighborhood size is irrelevant because the reduction above has no edges between selected vertices.