Est-ce que CMCG (graphique connecté au poids maximum) est un problème NP-complet?

Question

Problème MCG: Considérons un entier positif R et un graphique non dirigé g= (V, E), dans lequel chaque sommet est attribué un poids (ou une valeur). Le problème du graphique (MCG) connecté maximum (MCG) est de trouver un sous-graphique avec r sommets connectés et optimise la somme des poids (ou des valeurs) des sommets R.

Problème CMCG: Le problème de la CMCG est le problème de la MCG avec une contrainte d'un sommet prédéterminé (fixe) inclus dans la solution.

dans 1 Il a été indiqué (premier paragraphe, section 1) que MCG est un problème complet, qui est prouvé dans [3] (Cependant, je n'ai pas pu trouver le rapport technique [3] n'importe où sur Internet).

in 2 Il a été "affirmé" que la CMCG est NP-complète (deuxième paragraphe dernier, section 3). Mais n'a fourni aucune preuve.

Je veux savoir (et voir une preuve, si possible) que si la CMCG est NP-complète.

dans 1 Il a été montré que le problème de l'arbre Steiner, qui est NP-complet est un cas particulier du problème de la CMCG. Cela implique-t-il que la CMCG est NP-Complete?

[3]: Lee, H. F. et D. R. DOLY. Le problème de graphique connecté au poids maximum. Rapport technique 93-4, Ingénierie industrielle, Université Sud de l'Illinois, 1993.

Answer 1

Premièrement, notez que vous pouvez réduire la réduction $ cmcg $ à $ mcg $ en définissant la valeur de la valeur deLe nœud qui doit être dans le réglage de la somme de tous les poids positifs de tous les autres nœuds $ + 1 $ puis appliquer $ MCG $ et récupérer le jeu de résultats.Ainsi $ cmcg \ in np $ .

Comme prouvé dans le papier, le problème $ NP $ -Complete steiner-arbre problème peut être réduit à $ cmcg $ Signification que $ CMCG $ est $ np $ -hard.Si un problème est dans $ NP $ et $ np $ -hard il est par définition $ np $ -Compléte.

J'espère que cela aide.