Qual é a complexidade desse problema gráfico?

Dado um gráfico simples e não direcionado , encontre um subconjunto de vértices, de modo que $G$ $A\neq \emptyset$

para qualquer vértice pelo menos metade dos vizinhos de também estão em , e $x\in A$ $x$ $A$
o tamanho de é mínimo. $A$

Ou seja, estamos procurando um cluster, no qual pelo menos metade da vizinhança de cada vértice interno permaneça interna. A mera existência de um cluster desse tipo é óbvia, pois todo o conjunto de vértices sempre possui a propriedade 1. Mas quão difícil é encontrar o menor (não vazio) cluster desse tipo? $V(G)$

Existe um nome padrão para esse problema? O que se sabe sobre sua complexidade?

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

Parece uma variante do problema de Partição Satisfatória . Não sei se sua variante é conhecida e foi provada ser NPC; mas, provavelmente, uma redução de k-clique deve funcionar: ligação cada nó

do gráfico original para

nodos de um

"clique externo" de tamanho

(cada nó tem a sua pequena associação externo). Então você pode encontrar um conjunto não trivial

de tamanho

se e somente se 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$ -clique existe no gráfico original (você deve escolher pelo menos um nó, mas deve evitar qualquer clique externo). Mas é apenas uma ideia; se tiver tempo suficiente, tentarei ver se a redução está correta.

Marzio De Biasi

@MarzioDeBiasi Obrigado, depois de algumas pesquisas, descobri que o Problema de Partição Satisfatória está realmente relacionado. No entanto, em todas as variantes que pude encontrar, elas procuram por uma partição, e não por um único conjunto. Não está claro como eles estão relacionados. Na sua redução, a menos que eu tenha entendido algo errado , uma

-ique do gráfico original não satisfaz a definição, já que cada nó terá

vizinhos internos, mas pelo menos

vizinhos externos, devido à adição externa adicionada panelinhas.

k

$k$

k - 1

$k-1$

k + 1

$k+1$

Andras Farago

Eu acho que este problema é conhecido como “aliança defensiva”

Daniello

@daniello: ótimo, procurei na pesquisa IG Yero, JA Rodriguez-Velazquez, "Alianças defensivas em gráficos: uma pesquisa", 2013, mas não encontrei a palavra "metade"; quando tiver tempo suficiente, lerei com atenção; é provável que o problema do OP já seja conhecido!

Marzio De Biasi

Parece ser formulado como "cada vértice tem pelo menos tantos vizinhos dentro como fora", que é o mesmo que na pergunta-se ao arredondamento, e, possivelmente incluindo / não incluindo o próprio vértice na contagem

Daniello

Respostas:

Esta é uma redução do Clique para o seu problema.

Começamos com um exemplo de Click: um gráfico que e um número inteiro , deixar . $G$ $k$ $V = \{ v_1, v_2,...,v_n\}$

Clique permanece NPC mesmo sob a restrição de que (esboço de prova: se em seguida, adicione um onde $max(deg(v_i)) \leq 2(k-1)$ $max(deg(v_i) > 2(k-1)$ $K_t$ e conecte-o a todos os nós de e solicite um clique do tamanho no novo gráfico). $t = 2(k-1) - max(deg(v_i))$ $G$ $k' = k + t$

Portanto, assumimos que em , . Para cada nó para o qual é criada uma "externo" clique de tamanho (cada nó de $G$ $max(deg(v_i)) \leq 2(k-1)$ $v_i$ $deg(v_i) < 2(k-1)$ $C_i$ $2(k+1)+1$ clique tem pelo menos vizinhos). $C_i$ $2(k+1)$

Se é o grau de , conectamos a nós de . $deg(v_i)$ $v_i$ $v_i$ $2(k-1) - deg(v_i)$ $C_i$

No resultante , cada possui grau ; so porque pelo menos um vértice deve ser selecionado. $G'$ $v_i$ $2(k-1)$ $|A| \geq k$

É claro que, se um dos vértices de é incluído em , em seguida, pelo menos nós também deve ser inserido na mesma. Note-se que, se um nó original tem então pelo menos um nó do ligadas deve ser incluído, levando a . $C_i$ $A$ $2(k+1)/2 = k+1$ $deg(v_i) < k-1$ $C_i$ $|A| > k$

Para que possamos construir um conjunto de tamanho mínimo se e somente se contiver um clique do tamanho . $A$ $|A| = k$ $G$ $k$

Um exemplo da redução em que perguntamos se o gráfico representado pelos nós amarelos e arestas em negrito contém uma clique do tamanho (um triângulo). $G$ $k = 3$

Os nós azuis (agrupados para melhor legibilidade) são , as bordas vermelhas são os elos entre os nós de com . $K_9$ $G$ $deg(v_i) < 2(k-1)$

Marzio De Biasi
fonte

@WillardZhan: como todo vértice de

tem grau

por construção, portanto, se

contém um vértice, ele deve conter pelo menos

vizinhos (e o mesmo aplica-se a todos os vértices de

), então

. O "tamanho mínimo"

pode ser alcançado apenas se

for um clique do tamanho

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: Adicionei outra condição ao problema de camarilha inicial (mas ele deve permanecer como NPC) ... ainda estou verificando (não estou totalmente convencido de que está correto).

Marzio De Biasi

Sim, agora funciona perfeitamente (embora deva ser

na expressão de

). Talvez eu deva excluir meus comentários?

k^{'}

$k'$

t

$t$

Willard Zhan

@WillardZhan: Acho que está correto, porque nesse parágrafo estou me referindo à redução de Clique [instância

] para Clique + restrição

[instância

é o número de nós (clique) a serem adicionados ao G para obter a nova instância do Clique que stastisfies a restrição.

(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