What is the complexity of this graph problem?
This is a reduction from Clique to your problem .

We start with an instance of Clique: a graph $G$ and an integer $k$, let $V = \{ v_1, v_2,...,v_n\}$.

Clique remains NPC even under the constraint that $max(deg(v_i)) \leq 2(k-1)$ (proof sketch: if $max(deg(v_i) &gt; 2(k-1)$ then add a $K_t$ where $t = 2(k-1) - max(deg(v_i))$ and connect it to all nodes of $G$ and ask for a clique of size $k' = k + t$ in the new graph). 

So we assume that in $G$, $max(deg(v_i)) \leq 2(k-1)$. For each node $v_i$ for which $deg(v_i) &lt; 2(k-1)$ we create an "external" clique $C_i$ of size $2(k+1)+1$ (every node of $C_i$ clique has at least $2(k+1)$ neighbours).

If $deg(v_i)$ is the degree of $v_i$, we connect $v_i$ to $2(k-1) - deg(v_i)$ nodes of $C_i$.

In the resulting $G'$, each $v_i$ has degree $2(k-1)$; so $|A| \geq k$ because at least one vertex must be selected.

It is clear that if one of the vertex of $C_i$ is included in $A$ then at least $2(k+1)/2 = k+1$ nodes must also be inserted in it. Note that if an original node has $deg(v_i) &lt; k-1$ then at least one node of the linked $C_i$ must be included, leading to $|A| &gt; k$. 

So we can build a set $A$ of minimum size $|A| = k$ if and only if $G$ contains a clique of size $k$.

An example of the reduction in which we ask if the graph $G$ represented by the yellow nodes and bold edges contains a clique of size $k = 3$ (a triangle).



The blue nodes (grouped for better readability) are $K_9$, the red edges are the links between nodes of $G$ with $deg(v_i) &lt; 2(k-1)$ .