16
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Marzio De Biasi Feb 20 '18 at 12:23
  • $\begingroup$ @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. $\endgroup$ – Andras Farago Feb 20 '18 at 17:37
  • 2
    $\begingroup$ I think this problem is known as “defensive alliance” $\endgroup$ – daniello Feb 21 '18 at 4:04
  • 1
    $\begingroup$ @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! $\endgroup$ – Marzio De Biasi Feb 21 '18 at 8:33
  • 2
    $\begingroup$ 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 $\endgroup$ – daniello Feb 21 '18 at 11:34
6
$\begingroup$

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

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

$\endgroup$
  • $\begingroup$ @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$. $\endgroup$ – Marzio De Biasi Feb 20 '18 at 22:43
  • $\begingroup$ @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). $\endgroup$ – Marzio De Biasi Feb 20 '18 at 23:41
  • 1
    $\begingroup$ Yes, now it works perfectly (though it should be $k'$ in the expression of $t$). Maybe I shall delete my comments? $\endgroup$ – Willard Zhan Feb 21 '18 at 3:22
  • $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Feb 21 '18 at 8:13

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.