What is the complexity of this graph problem? Given a simple undirected graph $G$, find a subset $A\neq \emptyset$ of vertices, such that 


for any vertex $x\in A$ at least half of the neighbors of $x$ are also in $A$, and 
the size of $A$ is minimum.


That is, we are looking for a cluster, in which at  least half of the neighborhood of every internal vertex stays internal. The mere existence of such a cluster is obvious, since the whole vertex set $V(G)$ always has property 1.
But how hard is it to find the smallest (nonempty) such cluster?

Is there a standard name for this problem? What is known about its complexity?
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)$ .