È CMCG (grafico con connessione con peso massimo limitato) Problema NP-Completa?

Question

Problema MCG: considerare un numero intero positivo r e un grafico non rilevato G= (V, E), in cui ogni vertice viene assegnato un peso (o valore). Il problema del grafico del grafico del peso massimo (MCG) del peso massimo è trovare un sottogramma con r vertici che è collegato e massimizza la somma dei pesi (o valori) dei vertici R.

Problema CMCG: il problema CMCG è il problema MCG con un vincolo di un vertice predeterminato (fisso) incluso nella soluzione.

in 1 è stato dichiarato (primo paragrafo, sezione 1) che MCG è un problema completo di NP, che è dimostrato in [3] (Tuttavia non ho potuto trovare il rapporto tecnico [3] ovunque su Internet).

in 2 È stato "rivendicato" che CMCG è NP-Completa (secondo all'ultimo paragrafo, sezione 3). Ma non ha fornito alcuna prova.

Voglio sapere (e vedere una prova, se possibile) che se CMCG è completa di NP.

in 1 È stato dimostrato che il problema dell'albero STEINER, che è NP-completo è un caso speciale del problema CMCG. Implica che CMCG è NP-Complete?

[3]: Lee, H. F. e D. R. Dooly. Il problema del grafico del peso massimo. Rapporto tecnico 93-4, Ingegneria industriale, Università del Southern Illinois, 1993.

Answer 1

Prima, nota che è possibile ridurre $ cmcg $ a $ MCG $ impostando il valore diIl nodo che deve essere nel set sulla somma di tutti i pesi positivi di tutti gli altri nodi $ + 1 $ e quindi applicare $ MCG $ e recuperando il set di risultati.Quindi $ cmcg \ in np $ .

Come dimostrato nella carta la $ NP $ -Complete Steiner-Tree Problems può essere ridotto a $ cmcg $ Significa che $ cmcg $ è $ NP $ -Hard.Se un problema è in $ NP $ e $ NP $ -Hard è per definizione $ NP $ -Complete.

Spero che questo aiuti.