ما هو تعقيد مشكلة K-Clique مع قمة محددة سلفا في الحل؟

Question

clique (من wikipedia):

clique هي مجموعة فرعية من رؤوس الرسم البياني غير المعالج مثل كل ذلك اثنين من القمم المميزة في الزمرة مجاورة؛وهذا هو، مستحث لها subgraph كاملة.

k-clique مشكلة: العثور على زمرة من الحجم K. هذا هو np-complete وفقا ل Wiki،

قد درس الصلطرات أيضا في علوم الكمبيوتر: العثور على ما إذا كان هناك زمرة من حجم معين في الرسم البياني (مشكلة الزمرة) كاملة، ولكن على الرغم من أن هذه الصلابة تؤدي إلى دراسة العديد من الخوارزميات لإيجاد الزمرات.

اسمحوا لنا بالنظر في "مشكلة K-Clique" - وهي مشكلة K-Clique مع وجود قيود على وجود قسط محدد مسبقا مدرجا في الحل.ماذا سيكون تعقيد هذه المشكلة؟هل هي مشكلة معروفة في الأدب؟

Answer 1

لا يزال $ \ mathsf {np} $ -complete. النظر في التخفيض التالي من $ \ mathrm {clique} $ المشكلة: بالنظر إلى الرسم البياني $ g $ حجم الزمرة المطلوب $ K $ ، أضف قمة جديدة $ v ^ \ AST $ والتي ترتبط بجميع رؤوس $ g $ للحصول على رسم بياني جديد $ g ^ \ AST $ . ثم $ (g ^ \ ast، k + 1، v ^ \ ast) $ هو مثيل نعم لتعديل $ \ Mathrm {clique} $ مشكلة إذا وفقط إذا كان $ (g، k) $ هو مثيل نعم من $ \ mathrm {clique} $ .