O problema do CMCG (gráfico de peso máximo restrito) NP-completo?

Question

MCG Problema: Considere um inteiro positivo e um gráfico não direcionado g= (v, e), no qual cada vértice recebe um peso (ou valor). O problema do gráfico de peso máximo conectado (MCG) é encontrar um subgraph com v vértices conectados e maximiza a soma dos pesos (ou valores) dos vértices R.

CMCG Problema: O problema do CMCG é o problema do MCG com uma restrição de ter um vértice predeterminado (fixo) incluído na solução.

em 1 <<< Foi declarado (primeiro parágrafo, seção 1) que o MCG é um problema NP-completo, que é provado em [3] (No entanto, não consegui encontrar o relatório técnico [3] em qualquer lugar da Internet).

em 2 Foi "reivindicado" que a CMCG é NP-completa (segundo ao último parágrafo, seção 3). Mas não forneceu nenhuma prova.

Eu quero saber (e ver uma prova, se possível) que, se o CMCG for NP-completo.

em 1 Foi demonstrado que o problema da árvore de steiner, que é NP-completo é um caso especial do problema do CMCG. Isso implica que o CMCG é NP-completo?

[3]: Lee, H. F., e D. R. Doly. O problema do gráfico conectado máximo de peso. Relatório Técnico 93-4, Engenharia Industrial, Universidade do Sul da Illinois, 1993.

Answer 1

Em primeiro lugar, observe que você pode reduzir $ cmcg $ para $ mcg $ definindo o valor deO nó que deve estar no conjunto para a soma de todos os pesos positivos de todos os outros nós $ 1 $ e, em seguida, aplicando $ Mcg $ e recuperando o conjunto de resultados.Assim, $ cmcg \ em np $ .

como provado no papel a $ NP $ -complete problema de árvore de steiner pode ser reduzido para $ cmcg $ significado que $ cmcg $ é $ NP $ -hard.Se um problema estiver em $ NP $ e $ NP $ -Hard é por definição $ NP $ -complete.

Espero que isso ajude.