CMCG（拘束最大重量接続グラフ）問題NP-Completeですか？

Question

MCG問題：正の整数Rと無向グラフG=（V、E）を考えて、各頂点に重み（または値）が割り当てられている。最大重み接続グラフ（MCG）問題 接続されているR個の頂点を持つサブグラフを見つけることです。 R個の頂点の（または値）

CMCG問題：CMCG問題は、解決策に含まれる所定の（固定）頂点を有するという制約を有するMCG問題である。

1 MCGがNP完全な問題であることが記載されている（最初の段落、セクション1）。 [3]（ただし、インターネット上の任意の場所での技術レポート[3]が見つかりませんでした）。

1 NP完成であるSteinerツリーの問題は、CMCG問題の特別な場合であることが示されています。 CMCGがNP完成品であることを意味しますか？

[3]：Lee、H。F.、およびD.R.Doly。最大重み付けグラフ問題。技術報告書93-4、南イリノイ大学南部産業工学。

Answer 1

最初に、 $ cmcg $ を $ mcg $ に縮小できることに注意してください。その他のすべてのノードのすべての正の重みの合計に設定されている必要があるノードは、 $ + 1 $ を適用してから$ MCG $ と結果セットを取得します。したがって、 $ cmcg \ in np $ 。

論文で証明されたように $ np $ - Complete Steiner-Treeの問題は $ cmcg $ $ cmcg $ は、 $ np $ --hardです。問題が $ np $ および $ np $ --hardの場合、定義 $ NP $ - Complete。

これが役立つことを願っています。