Il problema CMCG (Constrained Maximum-Weight Connected Graph) è NP-completo?

Question

Problema MCG: si consideri un intero positivo R e un grafo non orientato G = (V, E), in cui a ciascun vertice è assegnato un peso (o valore). Il problema del grafo connesso a peso massimo (MCG) è trovare un sottografo con vertici R che sia connesso e massimizzi la somma dei pesi (o valori) dei vertici R.

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

In 1 è stato affermato (Primo paragrafo, Sezione 1) che MCG è un problema NP-completo, che è dimostrato in [3] (Tuttavia non sono riuscito a trovare la relazione tecnica [3] da nessuna parte su Internet).

In 2 è stato "affermato" che CMCG è NP-completo (dal secondo all'ultimo paragrafo, sezione 3). Ma non ha fornito alcuna prova.

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

In 1 è stato dimostrato che il problema dell'albero di Steiner, che è NP-completo, è un caso speciale del problema CMCG. Significa che CMCG è NP-completo?

[3]: Lee, HF e DR Dooly. Il problema del grafico connesso al peso massimo. Rapporto tecnico 93-4, Ingegneria industriale, Southern Illinois University, 1993.

Answer 1

In primo luogo, nota che puoi ridurre $CMCG$ per $MCG$ impostando il valore del nodo che deve essere nell'insieme alla somma di tutti i pesi positivi di tutti gli altri nodi $+1$ e quindi applicare $MCG$e recuperare il set di risultati. Così$CMCG\in NP$.

Come dimostrato nel documento, il file $NP$-Il problema completo di Steiner-Tree può essere ridotto a $CMCG$ intendendo che $CMCG$ è $NP$-difficile. Se c'è un problema in$NP$ e $NP$-duro è per definizione $NP$-completare.

Spero che sia di aiuto.