حل Exact2IS باستخدام هي

Question

واجهتني المشكلة التالية:

Exact2IS ={G بالضبط 2 المستقلة مجموعات}

على افتراض أنه بالنظر إلى الرسم البياني ز يمكنني العثور على مجموعة مستقلة كيف يمكنني معرفة ما إذا ز بالضبط 2 مجموعات مستقلة.

(أنا يمكن أن تحقق إذا كان الرسم البياني يحتوي على مجموعة مستقلة في س(1) و أيضا تجد بعض المستقلين في مجموعة س(1))

كنت أفكر في العثور على بعض المستقلة مجموعة(إذا كان هناك أي) من حجم k ثم إزالة قمة واحدة من مجموعة والتحقق إذا كان الرسم لا يزال لديه مجموعة مستقلة من حجم k -بعد أن تحقق أعود قمة الرأس إلى الرسم البياني كما كانت بالضبط.

المشكلة فكرتي تحقق إلا إذا كان الرسم البياني غرام تحتوي على ما لا يقل عن 2 مجموعات مستقلة وليس بالضبط.

أي شخص لديه فكرة كيف يمكنني معرفة ما إذا كان الرسم البياني بالضبط 2 المستقلة مجموعات(في وقت متعدد الحدود ونظرا لحقيقة أن تجد ومعرفة ما اذا كان هناك مجموعة مستقلة O(1))?

أي أدلة أو الأفكار سوف يكون موضع تقدير :) شكرا

Answer 1

أولا وقبل كل شيء، إذا كنت تستطيع تحديد ما إذا كان الرسم البياني $ g $ يحتوي على مجموعة مستقلة من الحجم $ k $ ، ثم يمكنك أيضا العثور على مثل هذه المجموعة بكفاءة. وهذا يعرف باسم "تخفيض البحث إلى القرار". هنا هي الفكرة الأساسية. اختر تقنية الرأس التعسفي $ v $ ، وإزالته. إذا كان الرسم البياني لا يزال لديه مجموعة مستقلة من الحجم $ k $ ، ثم استمر. خلاف ذلك، جميع مجموعات المستقلة من الحجم $ k $ تحتوي على $ v $ . وفقا لذلك، قم بإزالة $ v $ وجميع جيرانها، والعثور على مجموعة مستقلة من الحجم $ K-1 $ في الرسم البياني المتبقي. بهذه الطريقة، يمكنك استرداد مجموعة مستقلة من الحجم $ k $ .

ثانية، وكيفية التحقق مما إذا كان الرسم البياني يحتوي على على الأقل مجموعتين مستقلتين من الحجم $ K $ ، على افتراض $ k \ geq 2 $ . أولا، تحدد ما إذا كان في يحتوي على واحد على الأقل. لنفترض أنه يفعل ذلك، قل $ i $ . إذا $ J $ هي أي مجموعة مستقلة أخرى، ثم $ i \ setminus j $ و $ J \ setminus i $ غير مؤثرين (منذ $ | أنا |= | J | $ ). على وجه الخصوص، إذا $ x \ in i \ setminus j $ and $ y $ هو أي قمة أخرى في $ i $ ، ثم حتى بعد إضافة الحافة $ (x، y) $ Class="حاوية الرياضيات"> سوف تشكل $ J $ مجموعة مستقلة.

هذا يؤدي إلى الخوارزمية التالية: لكل زوج من القمم $ x، y \ in i $ $ ، حدد ما إذا كانت $ g + (x، y) $ يحتوي على مجموعة مستقلة من الحجم $ K $ . إذا كان الأمر كذلك، فإن هذه المجموعة المستقلة مختلفة بالضرورة عن $ i $ $ . على العكس من ذلك، إذا كانت مجموعة مستقلة من الحجم $ K $ مختلفة عن $ i $ $ موجودة، ثم بالضرورة سوف أن تكون مجموعة مستقلة في $ g + (x، y) $ للحصول على بعض $ x، y \ in i $ .

الثالث، وكيفية التحقق مما إذا كان الرسم البياني يحتوي على بالضبط اثنين من مجموعات مستقلة من الحجم $ K $ . هذا هو نفسه التحقق مما إذا كان الرسم البياني يحتوي على مجموعات على الأقل على الأقل. أعتقد أنه في هذه المرحلة، من الأفضل أن تحاول تعميم الوسيطة المذكورة أعلاه من مجموعتين إلى ثلاث مجموعات مستقلة. قد تتعثر، لكنك لن تعرف حتى تحاول.

Answer 2

إذا كان مسموح لك البحث وهو من الحجم $k$ في $\mathcal O(1)$, ثم ما عليك هو مكتوب تقريبا الحل.فقط مرتين تجد من حجم $k$, و بعد أن تحقق لمعرفة ما إذا كان لا يزال هناك واحد آخر.

ولكن عادة ، oracle آلات لا يسمح لك العثور على (في هذا المثال) هو داخل $\mathcal O(1)$ الوقت ، و يسمح لك فقط تحقق مما إذا كان أحد موجود داخل $\mathcal O(1)$.

آمل أن يساعد هذا!