Это CMCG (ограниченный максимальный вес подключенного графа) проблемы NP-Complete?

Question

MCG Проблема: рассмотрите положительное целое число R и неопроверженного графа G= (V, E), в которых каждая вершина присваивается вес (или значение). Проблема, связанная с максимально весом (MCG) это найти подграф с вершинами R, который подключен и максимизирует сумму весов (или значения) вершин R.

CMCG Проблема: проблема CMCG - это проблема MCG с ограничением определенной заданной (фиксированной) вершины, включенной в раствор.

в 1 Он был указан (первый абзац, раздел 1), который MCG является проблемой полной NP, которая доказана в [3] (однако я не смог найти Технический отчет [3] в любом месте в интернете).

в 2 Был «утвержден», что CMCG является NP-Complete (второй к последнему абзацу, раздел 3). Но не предоставил никаких доказательств.

Я хочу знать (и увидеть доказательство, если это возможно), что если CMCG NP-Class.

в 1 Было показано, что проблема дерева Штейнера, которая является NP-Complete, является специальным случаем задачи CMCG. Подразумевает ли это, что CMCG NP-Complete?

[3]: Ли, Х. Ф. и Д. Р. ДООли. Проблема, связанная с максимально весом. Технический отчет 93-4, промышленный инжиниринг, Южный университет Иллинойса, 1993.

Answer 1

Во-первых, обратите внимание, что вы можете уменьшить $ cmcg $ на $ mcg $ путем установки значенияУзел, который должен быть в установленном на сумму всех положительных весов всех других узлов $ + 1 $ , а затем применяя $ Mcg $ и извлечение набора результатов.Таким образом, $ cmcg \ in np $ .

Как доказано в документе $ NP $ - Предметание задачи STEINER может быть уменьшена до $ cmcg $ означает, что $ cmcg $ - $ NP $ -hard.Если проблема в $ np $ и $ np $ - это по определению $ NP $ -COMPLETE.

Надеюсь, это поможет.