الوقت تعقيد غطاء الرأس vs clique ل

Question

لدي 2 طرق لحل مشكلة مجموعة مستقلة للحجم الثابت $ k $ for graph $ g= (v،ه) $ :
- خوارزمية غطاء الرأس تعمل في $ O ^ * (1.47 ^ {v - k}) $ (خوارزمية متكررة محسنة)
- خوارزمية Clique تعمل في $ O ({v \ اختر k}) $ (مجموعة فرعية $ v $ وتحقق من الخوارزمية)

كيف يمكنني تحديد أي واحد لديه تعقيد وقت أقل؟أنا لست على دراية جدا بخوارزميات للمشاكل NP كاملة و $ o ^ * $ التدوين.من شأنه أن يخطط لهذه المهام يكفي؟أعتقد أن خوارزمية VC يمكن أن يكون لها أي مادة متعددة الحدود $ n ^ {o (1)} $ كضرب بسبب $o ^ * $ يمكن أن يؤثر ذلك على أوقات التشغيل، لكنني لست متأكدا.

Answer 1

لأي

$ k $ ، $ O (\ binom {v} {k})= o (v^ K) $ هو متعدد الحدود، في حين $ O ^ * (1.47 ^ {vk})= o ^ * (1.47 ^ v) $ هو الأسي.الأسية تنمو أسرع بكثير من متعدد الحدود.

تخطط المنحنيات غير مفيدة للغاية، لأن هذه هي عبارات مقارب.

قال، إذا كنت مهتما خاص $ v $ و $ k$ ، ثم خيارك الأفضل هو التحقق تجريبيا أي من هذه الخوارزميات أسرع.تدوين مقارب غير مفيد هنا، لأنه يخفي العوامل المستمرة، ويمكن أن تحدث هذه فرقا كبيرا لقيم الخرسانة من $ v $ و $ k $ .

Answer 2

غطاء

قمة الرأس هو المعلمة الثابتة المسموح بها. هناك $ 2 ^ k n $ الخوارزمية للعثور على VC من الحجم $ K $ . هذا يجب أن تغلب على الخوارزمية الساذجة. الحالة الحالية للفن هي شيء مثل 1.24 $ ^ k n $ .

تحت بعض الافتراضات، لا توجد خوارزمية ل Klique K مع وقت التشغيل $ f (k) n ^ c $ .

إذا كان الرسم البياني الخاص بك يحتوي على بعض الهيكل الخاص، فيمكن تحسين النتائج.