هل هناك أي معروف W[3] أو W[3]-من الصعب مشاكل ؟

Question

ونحن نعمل حاليا على البديل من الهيمنة المعلمة و أظهرنا أنه في W[3] فيما يتعلق معلمات التعقيد.أن ث[3]-كاملة, يجب أن تظهر المشكلة W[3] بجد أنا.ه ، أن تقلل من المعروف بالفعل W[3] مشكلة صعبة لنا.ولكن على عكس W[1] W[2] حيث الشهيرة في العديد من المشاكل أثبتت تلك الفئات ، من المستغرب أننا لم تأتي عبر واحد المشكلة W[3] بجد و لا حتى في مجرد W[3].بالطبع هناك عامة ث[t] الحالة التي نحن يمكن أن تذهب ، ولكن أي نتيجة W[3] على وجه الخصوص من شأنه أن يساعد كثيرا.

Answer 1

هناك عدد قليل من الأمثلة في جواب الطبيعية كاملة المشاكل في مستويات أعلى من W-التسلسل الهرمي.على وجه الخصوص ، ث[3]-كاملة المشكلة $p$-HYPERGRAPH-(غير)-الهيمنة-مجموعة قد يكون من المفيد للحصول على دليل الخاص بك.

بالنظر إلى أن يرتبط السؤال الآن ما يقرب من 6 سنوات من العمر, كنت ربما نتوقع بعض الأمثلة أكثر من أن يطفو على السطح الآن.ومع ذلك لم أستطع العثور على أي شيء ملموس بطريقة سريعة الأدب البحث.أقرب ما يمكن أن تجد فصل مجموعات من السلاسل من خلال إيجاد مطابقة أنماط هي دائما تقريبا بجد (2017) من قبل لانسيا وآخرون ، حيث التخمين أن المشكلة يسمونه تحديد نمط هو W[3]-كاملة عن معلمة معينة ، ولكن هذا التخمين هو ربما ليس من المفيد جدا بالنسبة دليل الخاص بك.أفعل علما بأنني لست خبيرا في هذا المجال ، لذلك قد يكون هناك بعض النتائج الأخيرة هناك أنا ببساطة لم تكن قادرة على العثور على.