تخفيض من قمة الرأس إلى مجموعة المهيمنة

Question

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

السؤال الذي أود طرحه هو، إذا قمنا بإسقاط رؤوس معزولة في المدخلات إلى مشكلة المهيمنة المحددة، فيمكننا بسهولة العثور على نموذج مضاد للتخفيض - دع المدخلات إلى مشكلة غطاء الرأس تكون بيانيا تحتوي على $ n $ العقد المعزولة والمعلمة $ k= n $ . الآن، ستكون المدخلات للمشكلة المحددة المهنة بيانا بيانيا فارغة مع المعلمة $ k= n $ . الآن، هناك غطاء رأس من الحجم $ n $ . لكنها ليست مجموعة هيمنة من الرسم البياني المحول (أي الإجابة على مشكلة غطاء الرأس هو نعم ولكن الإجابة على مشكلة الهيمنة مجموعة الغلاف غير موجود).

كيف يمكنني إصلاح التخفيض؟ هل يمكن لشخص ما يرجى تقديم المشورة لي؟

Answer 1

إذا فهمت بشكل صحيح، فلديك فقط مشكلة عندما يكون الرسم البياني $ g= (v، e) $ مثيل Certex-cover. في هذه الحالة، يمكنك تحويل $ G $ في الرسم البياني ذي الصلة $ g '= (v \ cup \ {x، y \}، E ') $ عن طريق إضافة اثنين من القمم الجديدة $ x $ و $ y $ مثل $ x $ و $ Y $ متصلة ببعضها البعض بواسطة حافة، وهناك هي حافة بين $ X $ وكل شيء آخر قمة الرأس في $ v $ . رسميا: $ e '= e \ cup \ {(x، v) \ mile v \ in v \ cup \ {cup \} $ .

إذا كان $ G $ يغطي غطاء الرأس $ C $ الحجم على الأكثر $ k $ ، ثم $ G '$ يعترف بجدار قمة الرأس في معظم $ k + 1 $ ، وهي $ c \ cup \ {x \} $ .

إذا كان $ g '$ يعترف بتقسيم غطاء الرأس $ c $ الحجم في معظم $ k + 1 $ ، ثم $ G $ يعترف بغطاء قمة الرأس في معظم $ K $ . يمكن أن ينظر إليه بسهولة من خلال ملاحظة أن $ c \ setminus \ {x، y \} $ يجب أن تغطي جميع الحواف في $ E $ ، وهذا $ (x، y) \ in e '$ يضمن أن واحد على الأقل من $ x $ and $ y $ موجود في $ c $ ، أي $ | c \ setminus \ {x، y \} |= | C | - | C \ CAP \ {x، y \} | \ le | c | - 1 \ Le K $ .

منذ $ G '$ لا يوجد لديه قمة معزولة، يمكنك الآن تحويله بأمان إلى الرسم البياني $ h $ < / SPAN> المثيل المهيمن (باستخدام التخفيض المعروف). بهذه الطريقة تظهر أن $ g $ لديه غطاء الرأس من الحجم على الأكثر $ K $ < Span Class="حاوية الرياضيات"> $ \ IFF $ $ H $ لديه مجموعة من الحجم الهيمنة في معظم $ k + 1 $ .