O problema CMCG (Constrained Maximum-Weight Connected Graph) é NP-completo?

Question

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

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

Em 1 foi afirmado (primeiro parágrafo, seção 1) que o MCG é um problema NP-completo, o que é comprovado em [3] (no entanto, não consegui encontrar o relatório técnico [3] em nenhum lugar da Internet).

Em 2 foi "afirmado" que CMCG é NP-completo (penúltimo parágrafo, Seção 3). Mas não forneceu nenhuma prova.

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

Em 1 , foi mostrado que o problema da árvore de Steiner, que é NP-completo, é um caso especial do problema CMCG. Isso implica que CMCG é NP-completo?

[3]: Lee, HF e DR Dooly. O problema do gráfico conectado de peso máximo. Relatório Técnico 93-4, Engenharia Industrial, Southern Illinois University, 1993.

Answer 1

Em primeiro lugar, observe que você pode reduzir $CMCG$ para $MCG$ definindo o valor do nó que deve estar no conjunto para a soma de todos os pesos positivos de todos os outros nós $+1$ e então aplicando $MCG$e recuperando o conjunto de resultados. portanto$CMCG\in NP$.

Conforme comprovado no jornal, $NP$- o problema Steiner-Tree completo pode ser reduzido a $CMCG$ significa que $CMCG$ é $NP$-Difícil. Se um problema está em$NP$ e $NP$-difícil é por definição $NP$-completo.

Espero que isto ajude.