# What is the complexity of this graph problem?

Given a simple undirected graph $G$, find a subset $A\neq \emptyset$ of vertices, such that

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

2. 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?

• It seems a variant of the Satisfactory Partition problem. I don't know if your variant is known and has been proved to be NPC; but probably a reduction from k-clique should work: link each node $v_i$ of the original graph to $k+1$ nodes of a $C_i$ "external clique" of size $2(k+1)$ (each node has its external clique). Then you can find a nontrivial set $A$ of size $k$ if and only if a $k$-clique exists in the original graph (you must pick at least a node, but you must avoid any external clique). But it is only an idea; if I have enough time I'll try to see if the reduction is correct. – Marzio De Biasi Feb 20 '18 at 12:23
• @MarzioDeBiasi Thank you, after some search I found out that the Satisfactory Partition Problem is indeed related. However, in every variant that I could find, they look for a partition, rather than for a single set. It is not clear, how they are related. In your reduction, unless I misunderstood something, a $k$-clique of the original graph does not satisfy the definition, since each node in it will have $k-1$ internal neighbors, but at least $k+1$ external neighbors, due to the added external cliques. – Andras Farago Feb 20 '18 at 17:37
• I think this problem is known as “defensive alliance” – daniello Feb 21 '18 at 4:04
• @daniello: great, I searched in the survey I.G. Yero, J.A. Rodriguez-Velazquez, "Defensive alliances in graphs: a survey", 2013 but didn't find the word "half"; when I have enough time I'll read it carefully; it's likely that the OP problem is alredy known! – Marzio De Biasi Feb 21 '18 at 8:33
• It seems to be formulated as "every vertex has at least as many neighbors inside as outside" which is same as in the question up to rounding, and possibly including/not including the vertex itself in the count – daniello Feb 21 '18 at 11:34

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) > 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) < 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) < k-1$ then at least one node of the linked $C_i$ must be included, leading to $|A| > 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) < 2(k-1)$ .

• @WillardZhan: because every vertex of $G'$ has degree $\geq 2(k-1)$ by construction, so if $A$ contain one vertex, it must contain at least $2(k-1)/2 = k-1$ neighbours (and the same applies to all vertices of $A$), so $|A| \geq k$. The "minimum size" $k$ can be achieved only if $A$ is a clique of size $k$. – Marzio De Biasi Feb 20 '18 at 22:43
• @WillardZhan: I added another condition to the starting clique problem (but it should remains NPC) ... I'm still checking it (not entirerly convinced its correct). – Marzio De Biasi Feb 20 '18 at 23:41
• Yes, now it works perfectly (though it should be $k'$ in the expression of $t$). Maybe I shall delete my comments? – Willard Zhan Feb 21 '18 at 3:22
• @WillardZhan: I think it's correct, because in that paragraph I'm referring to the reduction from Clique [instance $(G,k)$] to Clique+constraint $max(deg(v_i)) \leq 2(k-1)$ [instance $(G',k')$]. $t$ is the number of the nodes (clique) to add to G to get the new instance of Clique that stastisfies the constraint. – Marzio De Biasi Feb 21 '18 at 8:13