¿El problema de CMCG (gráfico conectado de peso máximo restringido) NP-Completa?

Question

MCG Problema: Considere un entero positivo R y un gráfico no discutible G= (V, E), en el que se le asigna cada vértice un peso (o valor). El problema de gráfico conectado de peso máximo (MCG) es encontrar un subgrafo con vértices R que esté conectado y maximice la suma de los pesos (o valores) de los vértices R.

Problema CMCG: El problema de CMCG es el problema MCG con una restricción de tener un vértice predeterminado (fijo) incluido en la solución.

en 1 se ha declarado (primer párrafo, sección 1) que MCG es un problema completo de NP, que se demuestra en [3] (Sin embargo, no pude encontrar el informe técnico [3] en cualquier lugar de Internet).

en 2 Se ha "reclamado" que CMCG es NP-completa (segundo al último párrafo, sección 3). Pero no proporcionó ninguna prueba.

Quiero saber (y ver una prueba, si es posible) que si CMCG es NP-Completa.

en 1 Se ha demostrado que el problema de Steiner Tree, que es NP-Completa es un caso especial del problema CMCG. ¿Implica que CMCG es NP-Completa?

[3]: Lee, H. F., y D. R. DOOLY. El problema del gráfico conectado de peso máximo. Informe técnico 93-4, Ingeniería Industrial, Universidad Sur de Illinois, 1993.

Answer 1

En primer lugar, tenga en cuenta que puede reducir $ cmcg $ a $ mcg $ al configurar el valor deEl nodo que debe estar en el conjunto en la suma de todos los pesos positivos de todos los otros nodos $ + 1 $ y luego aplicar $ Mcg $ y recuperando el conjunto de resultados.Por lo tanto $ cmcg \ en np $ .

Como se demostró en el documento el $ np $ -complete steiner-arbol de problema se puede reducir a $ cmcg $ lo que significa que $ cmcg $ es $ np $ -hard.Si un problema está en $ np $ y $ np $ -hard, es por definición $ NP $ -clete.

Espero que esto ayude.