Ist CMCG (eingeschränktes Maximalgewicht verbundenes Graph) Problem NP-COMPRETE?

Question

MCG-Problem: Betrachten Sie eine positive Ganzzahl R und einen ungerichteten Graphen G= (V, E), in dem jeder Scheitelpunkt ein Gewicht (oder einen Wert) zugeordnet ist. Das maximalgewicht angeschlossene Graph (MCG) -Problem ist, einen Untergraphen zu finden, der mit R-Scheitelpunkten, das miteinander verbunden ist, und maximiert die Summe der Gewichte (oder Werte) der R-Scheitelpunkte.

CMCG-Problem: Das CMCG-Problem ist das MCG-Problem mit einer Einschränkung eines vorbestimmten (festen) Scheitelpunkts, der in der Lösung enthalten ist.

in 1 Es wurde angegeben (erster Absatz 1), dass MCG ein NP-vollständige Problem ist, das in bewiesen ist [3] (Ich konnte jedoch den technischen Bericht [3] überall im Internet nicht finden).

in 2 Es wurde "beansprucht", dass CMCG NP-komplett ist (zweiter bis zum letzten Absatz Abschnitt 3). Gab jedoch keinen Beweis dafür.

Ich möchte wissen (und einen Beweis, wenn möglich), dass, wenn CMCG NP-komplett ist.

in 1 Es wurde gezeigt, dass Steiner-Baumproblem, das NP-Complete ist, ein Sonderfall des CMCG-Problems ist. Bedeutet es, dass CMCG NP-komplett ist?

[3]: Lee, H. F. und D. R. dooly. Das maximalgewicht angeschlossene Grafikproblem. Technischer Bericht 93-4, Industrietechnik, Süd-Illinois-Universität, 1993.

Answer 1

Erstens, beachten Sie, dass Sie $ CMCG $ auf $ MCG $ reduzieren können, indem Sie den Wert vonDer Knoten, der sich in der Soll-Summe aller positiven Gewichte aller anderen Knoten $ + 1 $ befindet, und dann auf Anwenden von $ Mcg $ und das Abrufen des Ergebnissatzes.Somit $ CMCG \ in NP $ .

, wie er in der Zeitung bewiesen ist Der $ NP $ -Complete Steiner-Tree-Problem kann auf $ cmcg $ bedeutet, dass $ cmcg $ $ NP $ -hard ist.Wenn sich ein Problem in $ NP $ und $ NP $ -hard befindet, ist es per Definition $ NP $ -Complete.

hoffe das hilft.