حل مجموعة مستقلة من خلال غطاء الرأس

Question

لدي مشكلة مجموعة مستقلة، لا بد لي من التحقق مما إذا كان الرسم البياني المعطى يحتوي على حجم معين الحجم $ K $ .لقد كتبت بالفعل خوارزمية غطاء الرأس لفترة واحدة وأتمنى أن أتمكن من إعادة استخدامه هنا.هذه الخوارزميات مرتبطة ارتباطا وثيقا، حيث إذا كان الرسم البياني $ g= (v، e) $ لديه حجم $ k $ IFF لديها VC من الحجم $ v - k $ .لذلك أنا على حق أنه يمكنني فقط استخدام خوارزمية VC الخاصة بي مع $ k '= v - k $ ؟

لقد قرأت هذا و هذا سؤال وبعد ذلك بدأت الشك في أن هذا بسيط.

Answer 1

هذا هو بهذه البساطة، هذه الأسئلة تتحدث عن الخوارزميات المسموح بها بالمعلمة الثابتة W.R.T.الحجم $ K $ غطاء مجموعة مستقل / قمة الرأس.الخوارزمية الخاصة بك سوف تعمل فقط على غرامة الإعداد $ k '= | الخامس |- K $ .من الواضح أن القيمة الجديدة $ K $ تؤثر أيضا على وقت تشغيل الخوارزمية الخاصة بك.