CMCG（约束最大重连接图）问题NP-Complete吗？

Question

mcg问题：考虑正整数r和一个无向图形g=（v，e），其中每个顶点被分配重量（或值）。最大重连接图（MCG）问题 是找到具有连接的R顶点的子图，并最大化权重的总和 R顶点的（或值）。

cmcg问题：CMCG问题是MCG问题，其约束具有包含在解决方案中的一个预定（固定）顶点的约束。

在 1

在 2 已被“声称”CMCG是NP-Chease（第二段，第3节）。但没有提供任何证据。

我想知道（并查看一个证明，如果可能的话）如果cmcg是np-complete。

在 1 已显示Steiner树问题，这是np-cleant是CMCG问题的特殊情况。它是否意味着CMCG是NP-Complete？

[3]：李，H. F.和D. R. Dooly。最大重连接的图形问题。 1993年南伊利诺伊州工业工程技术报告93-4 93-4。

Answer 1

首先，请注意，通过设置值，可以减少 $ cmcg $ to $ mcg $ 必须在设置为所有其他节点的所有正权力的节点 $ + 1 $ ，然后应用$ mcg $ 并检索结果集。因此，

中 $ cmcg \。

如图所示， $ np $ -complete Steiner-tree问题可以减少到 $ cmcg $ 意思是 $ cmcg $ 是 $ np $ -hard。如果问题是 $ np $ 和 $ np $ - 它是按定义 $ np $ -complete。

希望这有帮助。