¿Cuál es la complejidad de este problema gráfico?

Dado un gráfico no dirigido simple $G$ , encuentre un subconjunto $A\neq \emptyset$ de vértices, de modo que

para cualquier vértice al menos la mitad de los vecinos de también están en , y $x\in A$ $x$ $A$
El tamaño de es mínimo. $A$

Es decir, estamos buscando un grupo, en el que al menos la mitad del vecindario de cada vértice interno permanezca interno. La mera existencia de tal grupo es obvia, ya que todo el conjunto de vértices siempre tiene la propiedad 1. Pero, ¿qué tan difícil es encontrar el grupo más pequeño (no vacío)? $V(G)$

¿Existe un nombre estándar para este problema? ¿Qué se sabe sobre su complejidad?

graph-theory graph-algorithms np-hardness Andras Farago
fuente

Parece una variante del problema de partición satisfactoria . No sé si su variante es conocida y se ha demostrado que es NPC; pero probablemente una reducción de k-clique debería funcionar: vincula cada nodo

del gráfico original a

nodos de una "camarilla externa"

de tamaño

(cada nodo tiene su camarilla externa). Luego puede encontrar un conjunto no trivial

de tamaño

si y solo si a

v_{i}

$v_i$

k + 1

$k+1$

C_{i}

$C_i$

2 (k + 1)

$2(k+1)$

A

$A$

k

$k$

k

$k$ -la camarilla existe en el gráfico original (debe elegir al menos un nodo, pero debe evitar cualquier camarilla externa). Pero es solo una idea; si tengo suficiente tiempo, intentaré ver si la reducción es correcta.

Marzio De Biasi

@MarzioDeBiasi Gracias, después de una búsqueda descubrí que el problema de partición satisfactoria está relacionado. Sin embargo, en cada variante que pude encontrar, buscan una partición, en lugar de un solo conjunto. No está claro cómo están relacionados. En su reducción, a menos que haya entendido mal algo, una

-clique del gráfico original no satisface la definición, ya que cada nodo tendrá

vecinos internos, pero al menos

vecinos externos, debido a la agregación externa camarillas

k

$k$

k - 1

$k-1$

k + 1

$k+1$

Andras Farago

Creo que este problema se conoce como "alianza defensiva"

daniello

@daniello: genial, busqué en la encuesta IG Yero, JA Rodríguez-Velázquez, "Alianzas defensivas en gráficos: una encuesta", 2013 pero no encontré la palabra "mitad"; cuando tenga tiempo suficiente, lo leeré detenidamente; ¡es probable que el problema de OP ya sea conocido!

Marzio De Biasi

Parece formularse como "cada vértice tiene al menos tantos vecinos adentro como afuera", que es lo mismo que en la pregunta hasta el redondeo, y posiblemente incluye / no incluye el vértice mismo en el conteo

daniello

Respuestas:

Esta es una reducción de Clique a su problema.

Comenzamos con una instancia de Clique: una gráfica y un número entero , permiten . $G$ $k$ $V = \{ v_1, v_2,...,v_n\}$

Clique sigue siendo NPC incluso bajo la restricción de que (bosquejo de prueba: si luego agregue un donde $max(deg(v_i)) \leq 2(k-1)$ $max(deg(v_i) > 2(k-1)$ $K_t$ y conéctelo a todos los nodos de y solicite una camarilla de tamaño en el nuevo gráfico). $t = 2(k-1) - max(deg(v_i))$ $G$ $k' = k + t$

Entonces suponemos que en , . Para cada nodo para el que $G$ $max(deg(v_i)) \leq 2(k-1)$ $v_i$ creamos una camarilla "externa" de tamaño (cada nodo de $deg(v_i) < 2(k-1)$ $C_i$ $2(k+1)+1$ camarilla tiene al menos vecinos). $C_i$ $2(k+1)$

Si es el grado de , conectamos a nodos de . $deg(v_i)$ $v_i$ $v_i$ $2(k-1) - deg(v_i)$ $C_i$

En el resultante , cada tiene grado ; entonces porque se debe seleccionar al menos un vértice. $G'$ $v_i$ $2(k-1)$ $|A| \geq k$

Está claro que si uno de los vértices de está incluido en entonces al menos nodos también deben insertarse en él. Tenga en cuenta que si un nodo original tiene entonces debe incluirse al menos un nodo del vinculado , lo que lleva a . $C_i$ $A$ $2(k+1)/2 = k+1$ $deg(v_i) < k-1$ $C_i$ $|A| > k$

Entonces podemos construir un conjunto de tamaño mínimo si y solo si contiene una camarilla de tamaño . $A$ $|A| = k$ $G$ $k$

Un ejemplo de la reducción en la que preguntamos si el gráfico representado por los nodos amarillos y los bordes en negrita contiene una camarilla de tamaño (un triángulo). $G$ $k = 3$

Los nodos azules (agrupados para una mejor legibilidad) son , los bordes rojos son los enlaces entre los nodos de con . $K_9$ $G$ $deg(v_i) < 2(k-1)$

Marzio De Biasi
fuente

@WillardZhan: porque cada vértice de

tiene un grado

por construcción, por lo que si

contiene un vértice, debe contener al menos

vecinos (y el mismo se aplica a todos los vértices de

), entonces

. El "tamaño mínimo"

se puede lograr si

es una camarilla de tamaño

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$

A

$A$

k

$k$

Marzio De Biasi

@WillardZhan: Agregué otra condición al problema de la camarilla inicial (pero debería seguir siendo NPC) ... Todavía lo estoy comprobando (no estoy completamente convencido de que sea correcto).

Marzio De Biasi

Sí, ahora funciona perfectamente (aunque debería ser

en la expresión de

k^{'}

$k'$

t

$t$ ). ¿Quizás elimine mis comentarios?

Willard Zhan

@WillardZhan: Creo que es correcto, porque en ese párrafo me refiero a la reducción de Clique [instancia

] a Clique + restricción

[instancia

es el número de nodos (camarilla) que se agregará a G para obtener la nueva instancia de camarilla que confirma la restricción.

(G, k)

$(G,k)$

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

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

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

$(G',k')$

t

$t$

Marzio De Biasi