Ist das CMCG-Problem (Constrained Maximum-Weight Connected Graph) NP-vollständig?

Question

MCG-Problem: Betrachten Sie eine positive ganze Zahl R und einen ungerichteten Graphen G = (V, E), in dem jedem Scheitelpunkt eine Gewichtung (oder ein Wert) zugewiesen ist. Das Problem des maximal gewichteten verbundenen Graphen (MCG) besteht darin, einen Teilgraphen mit R Scheitelpunkten zu finden, der verbunden ist und die Summe der Gewichte (oder Werte) der R Scheitelpunkte maximiert.

CMCG-Problem: Das CMCG-Problem ist das MCG-Problem mit der Einschränkung, dass ein vorbestimmter (fester) Scheitelpunkt in der Lösung enthalten ist.

In 1 wurde festgestellt (erster Absatz, Abschnitt 1), dass MCG ein NP-vollständiges Problem ist, was in [3] bewiesen ist (ich konnte den technischen Bericht [3] jedoch nirgendwo im Internet finden).

In 2 wurde "behauptet", dass CMCG NP-vollständig ist (vorletzter Absatz, Abschnitt 3). Hat aber keinen Beweis erbracht.

Ich möchte wissen (und wenn möglich einen Beweis sehen), dass CMCG NP-vollständig ist.

In 1 wurde gezeigt, dass das Steiner-Baum-Problem, das NP-vollständig ist, ein Sonderfall des CMCG-Problems ist. Bedeutet dies, dass CMCG NP-vollständig ist?

[3]: Lee, HF und DR Dooly. Das Problem mit dem maximal verknüpften Diagramm. Technischer Bericht 93-4, Wirtschaftsingenieurwesen, Southern Illinois University, 1993.

Answer 1

Beachten Sie zunächst, dass Sie reduzieren können $CMCG$ zu $MCG$ indem Sie den Wert des Knotens, der in der Menge enthalten sein muss, auf die Summe aller positiven Gewichte aller anderen Knoten setzen $+1$ und dann bewerben $MCG$und Abrufen der Ergebnismenge. So$CMCG\in NP$.

Wie in der Zeitung bewiesen $NP$-vollständiges Steiner-Tree-Problem kann auf reduziert werden $CMCG$ bedeutet, dass $CMCG$ ist $NP$-schwer. Wenn ein Problem vorliegt$NP$ und $NP$-hard ist es per definitionem $NP$-Komplett.

Hoffe das hilft.