은 CMCG(제한 최대 중량이 연결된 그래프)문제가 NP-complete?

Question

MCG 문제가:고려한 양의 정수 R 무향 그래프 G=(V,전자)서,각 정점에 할당된 무게(또는 값).최대 무게 연결되는 그래프(MCG)문제 을 찾을 수 있 를 본다면 R 꼭지점이 연결되어 있는 극대화 합계 무게 (거나 값)의 R 꼭지점입니다.

CMCG 문제가:이 CMCG 문제입니다 MCG 문제가 제약 조건 중 하나를 갖는 소정의(고정)꼭짓점에 포함된 솔루션입니다.

에 1 그것은 명시되어 있(첫 번째 단락,Section1)는 MCG 은 NP-complete 문제는 증명서[3](그러나 나는 찾을 수 없는 기술적 보고서[3]어느 곳에서나 인터넷에서).

에 2 그것은"주"는 CMCG 은 NP-complete(마지막 단락 두 번째,3 절).하지 않았지만 어떤 증거를 제공하.

지 알고 싶(고 증명,가능하면)는 경우 CMCG 은 NP-complete.

에 1 그것을 보여왔는 슈타이너리,문제는 NP-complete 의 특별한 경우 CMCG 문제입니다.그것이 의미하는 CMCG 은 NP-complete?

[3]:Lee,H.F.,D.R.둘리'.최대 무게 연결되는 그래프는 문제입니다.기술 보고서 93-4,산업공학,Southern Illinois University,1993.

Answer 1

첫째,주를 줄일 수 있습니다 $CMCG$ 하기 $MCG$ 값을 설정해서는 노드에 있어야 합니다 설정 합계의 모든 긍정적인 무게의 모든 다른 노드 $+1$ 한 다음 적용 $MCG$ 검색 결과를 설정합니다.따라서 $CMCG\에 NP$.

으로 증명에서 종이 $NP$-전체 Steiner-트리 문제 감소될 수 있습니다 $CMCG$ 는 것을 의미 $CMCG$ 가 $NP$-어렵습니다.는 경우 문제에 $NP$ 고 $NP$-하드 그것은에 의해 정의 $NP$-이 완료합니다.

이게 도움이 되었으면 좋겠습니다.