<p>This is a reduction from Clique to your problem .</p>

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

<p>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). </p>

<p>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).</p>

<p>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$.</p>

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

<p>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$. </p>

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

<p>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).</p>

<p><a href="https://i.sstatic.net/4sIZ7.png" rel="noreferrer"><img src="https://i.sstatic.net/4sIZ7.png" alt="satisfactory problem variant 30CC0991E0BCCCD16E41CBD9CD3EEECC"></a></p>

<p>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)$ .</p>

CC BY-SA 3.0
2018-02-20T22:43:53.827Z
@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
CC BY-SA 3.0
2018-02-20T23:41:27.057Z
@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
CC BY-SA 3.0
2018-02-21T03:22:25.993Z
Yes, now it works perfectly (though it should be $k'$ in the expression of $t$). Maybe I shall delete my comments?
Wei Zhan
CC BY-SA 3.0
2018-02-21T08:13:00.813Z
@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
CC BY-SA 3.0
2018-02-20T19:23:08.350Z
2018-02-21T14:44:03.427Z
2018-02-21T14:44:03.427Z
Marzio De Biasi
<p>Given a simple undirected graph $G$, find a subset $A\neq \emptyset$ of vertices, such that </p>

<ol>
<li><p>for any vertex $x\in A$ at least half of the neighbors of $x$ are also in $A$, and </p></li>
<li><p>the size of $A$ is minimum.</p></li>
</ol>

<p>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?</p>

<p>Is there a standard name for this problem? What is known about its complexity?</p>

CC BY-SA 3.0
2018-02-20T12:23:04.893Z
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
CC BY-SA 3.0
2018-02-20T17:37:27.557Z
@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
CC BY-SA 3.0
2018-02-21T04:04:38.780Z
I think this problem is known as “defensive alliance”
daniello
CC BY-SA 3.0
2018-02-21T08:33:08.510Z
@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
CC BY-SA 3.0
2018-02-21T11:34:57.790Z
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
<graph-theory><graph-algorithms><np-hardness>
What is the complexity of this graph problem?
Andras Farago
# What is the complexity of this graph problem?

(Asked by: username_0 on 2018-02-19)

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?

**Tags:** graph-theory, graph-algorithms, np-hardness

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_2**: I think this problem is known as “defensive alliance”  
> **username_1**: @username_2: 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!  
> **username_2**: 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  

---

## 1 answers

### Answer by username_1 on 2018-02-20. Score: 8 | Accepted answer

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).

[![satisfactory problem variant 30CC0991E0BCCCD16E41CBD9CD3EEECC](https://i.sstatic.net/4sIZ7.png)](https://i.sstatic.net/4sIZ7.png)

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)$ .

> **Comments:**
> **username_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$.  
> **username_1**: @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).  
> **username_3**: Yes, now it works perfectly (though it should be $k'$ in the expression of $t$). Maybe I shall delete my comments?  
> **username_1**: @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.  

---

