Quelle est la complexité de ce problème graphique?

Étant donné un simple graphe non orienté $G$ , trouver un sous-ensemble $A\neq \emptyset$ de sommets, tel que

pour tout sommet $x\in A$ au moins la moitié des voisins de $x$ sont également dans $A$ , et
la taille de $A$ est minimale.

Autrement dit, nous recherchons un cluster, dans lequel au moins la moitié du voisinage de chaque sommet interne reste interne. La simple existence d'un tel cluster est évidente, car l'ensemble des sommets $V(G)$ toujours la propriété 1. Mais est-il difficile de trouver le plus petit (non vide) un tel cluster?

Existe-t-il un nom standard pour ce problème? Que sait-on de sa complexité?

graph-theory graph-algorithms np-hardness Andras Farago
la source

Cela semble être une variante du problème de partition satisfaisante . Je ne sais pas si votre variante est connue et s'est avérée être un PNJ; mais probablement une réduction de la k-clique devrait fonctionner: reliez chaque nœud

du graphe d'origine à

nœuds d'une "clique externe"

de taille

(chaque nœud a sa clique externe). Ensuite, vous pouvez trouver un ensemble non trivial

de taille

si et seulement si un

v_{i}

$v_i$

k + 1

$k+1$

C_{i}

$C_i$

2 (k + 1)

$2(k+1)$

A

$A$

k

$k$

k

$k$ -clique existe dans le graphique d'origine (vous devez choisir au moins un nœud, mais vous devez éviter toute clique externe). Mais ce n'est qu'une idée; si j'ai assez de temps, j'essaierai de voir si la réduction est correcte.

Marzio De Biasi

@MarzioDeBiasi Merci, après quelques recherches, j'ai découvert que le problème de partition satisfaisante est en effet lié. Cependant, dans chaque variante que j'ai pu trouver, ils recherchent une partition, plutôt qu'un seul ensemble. Il n'est pas clair, comment ils sont liés. Dans votre réduction, à moins que je ne comprenne quelque chose, une

-clique du graphe d'origine ne satisfait pas la définition, car chaque nœud aura des

voisins internes, mais au moins

voisins externes, en raison de l'ajout externe cliques.

k

$k$

k - 1

$k-1$

k + 1

$k+1$

Andras Farago

Je pense que ce problème est connu comme «alliance défensive»

daniello

@daniello: super, j'ai cherché dans l'enquête IG Yero, JA Rodriguez-Velazquez, "Alliances défensives dans les graphiques: une enquête", 2013 mais je n'ai pas trouvé le mot "moitié"; quand j'aurai assez de temps, je le lirai attentivement; il est probable que le problème OP est déjà connu!

Marzio De Biasi

Il semble être formulé comme «chaque sommet a au moins autant de voisins à l'intérieur qu'à l'extérieur», ce qui est le même que dans la question jusqu'à l'arrondi, et peut-être inclure / ne pas inclure le sommet lui-même dans le décompte

daniello

Réponses:

Il s'agit d'une réduction de Clique à votre problème.

Nous commençons par une instance de Clique: un graphe et un entier , laissez $G$ $k$ $V = \{ v_1, v_2,...,v_n\}$ .

La clique reste un PNJ même sous la contrainte que (esquisse de preuve: si puis ajoutez un où $max(deg(v_i)) \leq 2(k-1)$ $max(deg(v_i) > 2(k-1)$ $K_t$ et le connecter à tous les nœuds de et demander une clique de taille dans le nouveau graphe). $t = 2(k-1) - max(deg(v_i))$ $G$ $k' = k + t$

Nous supposons donc que dans , . Pour chaque nœud pour lequel on crée une clique "externe" de taille (chaque nœud de $G$ $max(deg(v_i)) \leq 2(k-1)$ $v_i$ $deg(v_i) < 2(k-1)$ $C_i$ $2(k+1)+1$ $C_i$ clique a au moins voisins). $2(k+1)$

Si est le degré de , nous connectons à nœuds de . $deg(v_i)$ $v_i$ $v_i$ $2(k-1) - deg(v_i)$ $C_i$

Dans le résultant , chaque a le degré ; donc car au moins un sommet doit être sélectionné. $G'$ $v_i$ $2(k-1)$ $|A| \geq k$

Il est clair que si l'un des sommets de est inclus dans alors au moins nœuds doivent également y être insérés. Notez que si un nœud d'origine a alors au moins un nœud du lié doit être inclus, conduisant à . $C_i$ $A$ $2(k+1)/2 = k+1$ $deg(v_i) < k-1$ $C_i$ $|A| > k$

Nous pouvons donc construire un ensemble de taille minimale si et seulement si contient une clique de taille . $A$ $|A| = k$ $G$ $k$

Un exemple de la réduction dans laquelle nous demandons si le graphe représenté par les nœuds jaunes et les bords gras contient une clique de taille (un triangle). $G$ $k = 3$

Les nœuds bleus (regroupés pour une meilleure lisibilité) sont , les bords rouges sont les liens entre les nœuds de avec . $K_9$ $G$ $deg(v_i) < 2(k-1)$

Marzio De Biasi
la source

G^{'}

$G'$

\geq 2 (k - 1)

$\geq 2(k-1)$

A

$A$

2 (k - 1) / 2 = k - 1

$2(k-1)/2 = k-1$

A

$A$

| A | \geq k

$|A| \geq k$

k

$k$ can be achieved only if

A

$A$ is a clique of size

k

$k$ .

Marzio De Biasi

@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

Yes, now it works perfectly (though it should be

k^{'}

$k'$ in the expression of

t

$t$ ). Maybe I shall delete my comments?

Willard Zhan

@WillardZhan: I think it's correct, because in that paragraph I'm referring to the reduction from Clique [instance

(G, k)

$(G,k)$ ] to Clique+constraint

m a x (d e g (v_{i})) \leq 2 (k - 1)

$max(deg(v_i)) \leq 2(k-1)$ [instance

(G^{'}, k^{'})

$(G',k')$ ].

t

$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