مشكلة NPC الحد الأدنى لمجموعة Certex Colling

Question

للحصول على الرسم البياني G و A CETTEX-COLDING ψ: V (G) → N من G،

دع σψ (g) يكون مجموع ψ (v)،

وتعيين σ (g):= min σψ (g)،

حيث يتراوح الحد الأدنى على جميع لونات قمة الرأس صالحة من G.

تثبت أن {(g، k): σ (g) ≤ k} npc.

فكرت في تخفيض من مجموع الفرع الفرعي ولكن مشكلتي مع الدفلة وليس مع المبلغ، وأنا لا أفهم كيفية القيام بتخفيض للتحقق من الحد الأدنى. حصلت على تلميح للقيام بتخفيض من 3-NAE-SAT لكنني لا أفهم كيف. سوف نقدر بعض المساعدة.حتى بعض المصدر يمكنني أن أقرأ حول هذه المشكلة إذا كنت تعرف عن شيء ما.

Answer 1

سنقوم بتقليل من 3Col، وهي المشكلة التالية: مع إعطاء رسم بياني، هل هو 3 قابلة للقروين؟

إعطاء الرسم البياني $ g= (v، e) $ ، نبني رسم بياني جديد $ g '$ < / span> on $ v \ times \ {1،2،3 \} $ ، التي حوافها $$ \ {((I، A)، (J، A)) \ MID (i، j) \ in e، a \ in [3] \} \ cup \ {((i، a)، (i، b) ) \ منتصف أنا \ في الخامس، 1 \ leq a بالكلمات، نأخذ ثلاث نسخ من $ G $ ، وتوصيل جميع نسخ من نفس Vertex.

إذا كان $ G $ هو 3 قابلة للظلام ثم $ G '$ يمكن أن يكون 3 ملون: نظرا لثلاث تلوينات $ \ chi $ من $ v $ ، اللون $ (I، A) $ مع اللون $ \ chi (i) + a \ bmod 3 $ . مجموع الألوان هو 6 دولارات | V | $ .

على العكس على العكس، افترض أن $ G '$ لديه اللون $ \ chi' $ 6 دولارات | V | $ . لاحظ أن النسخ الثلاث من كل قمة الرأس="حاوية الرياضيات"> $ (i، 1)، (i، 2)، (i، 3) $ يجب تعيين ألوان مختلفة، والتي تبلغ إلى على الأقل 6 دولارات $ . لذلك $ \ sigma \ chi '\ geq 6 | v | $ for أي التلوين $ \ chi '$ ، و $ \ sigma \ chi'= 6 | v | $ IFF $ \ chi ' $ هو 3 تلوين. بالنظر إلى واحدة من نسخ نسخ $ g $ ، نرى أن $ g $ هو 3 قابلة للقرونة. < / ص>