هل CMCG (الرسم البياني الأقصى المتصل الوزن) مشكلة NP-Complete؟

Question

mcg مشكلة: النظر في عدد صحيح إيجابي ص الرسمي الرسمي G= (v، E)، حيث يتم تعيين كل قمة وزن (أو قيمة). مشكلة الرسم البياني المرتبط الأقصى للوزن (MCG) هو العثور على مجموعة فرعية مع Reats R متصل ويزيد مجموع الأوزان (أو قيم) من القمم r.

مشكلة CMCG: مشكلة CMCG هي مشكلة MCG مع عائق وجود قمة واحدة محددة مسبقا (ثابتة) مدرجة في الحل.

في 1 تم ذكرها (الفقرة الأولى، القسم 1) أن MCG مشكلة كاملة، والتي ثبت فيها [3] (ومع ذلك لم أتمكن من العثور على التقرير الفني [3] في أي مكان على الإنترنت).

في 2 لقد تم "المطالبة" بأن CMCG هو np-complete (ثانية إلى الفقرة الأخيرة، القسم 3). ولكن لم تقدم أي دليل.

أريد أن أعرف (ورؤية دليلا، إن أمكن، إذا كان CMCG أكمل NP.

في 1 تم عرض مشكلة شجرة شتاينر، وهي NP-Complete هي حالة خاصة لمشكلة CMCG. هل يعني أن CMCG هو np-complete؟

[3]: Lee، H. F.، D. R. Dooly. مشكلة الرسم البياني الموجود في الوزن الأقصى. التقرير الفني 93-4، الهندسة الصناعية، جامعة إلينوي الجنوبية، 1993.

Answer 1

أولا، لاحظ أنه يمكنك تقليل $ CMCG $ إلى $ mcg $ عن طريق تحديد قيمةالعقدة التي يجب أن تكون في المجموعة المقدمة إلى مجموع جميع الأوزان الإيجابية لجميع العقد الأخرى $ + 1 $ ثم تطبيق $ MCG $ واسترجأ مجموعة النتائج.هكذا $ cmcg \ in np $ .

كما ثبت في الورق $ NP $ يمكن تخفيض مشكلة شجرة شتاينر (SPAN Class="حاوية الرياضيات"> $ CMCG $ معنى أن $ cmcg $ هو $ NP $ -Hard.إذا كانت هناك مشكلة في $ NP $ and $ NP $ -Hard بحكم التعريف $ NP $ -complete.

نأمل أن يساعد هذا.