مجموعات مشبعة في الرسم البياني في bipartite

Question

دع $ g= (x \ cup y، e) $ يكون رسم بياني ثنائي الفحم غير المرجح. نحن نعطى ذلك لكل $ w \ subseteq x $ يحمل أن $ | W | \ leq | N (W) N (W) N (W) N (W) | $ ، حيث $ n (w) $ هو الجيران من $ W $ في $ y $ (حالة زواج القاعة المعروفة اه).

هدفي هو العثور على مجموعة فرعية $ w ^ * \ subseteq x $ مع $ | w ^ * |= | N (W ^ *) | $ ، إذا كانت هذه المجموعة الفرعية موجودة (من الواضح أنها لا تحتاج غير موجودة). نظرا لأنني لست على علم باسم رسمي لهذا العقار، فسأشير إلى مثل هذا $ w ^ * $ ك مجموعة مشبعة .

الأسئلة:

1. هل هذا العقار معروف على نطاق واسع؟ هل لديها اسم مختلف؟
2. على افتراض أن حالة الزواج يحمل، فهو واضح لإظهار أن كل اتحاد من مجموعات المشبعة مشبعة أيضا. مشكلة واحدة مثيرة للاهتمام هي العثور على الحد الأقصى للمجموعة المشبعة. أصفت أدناه محلول ساذج إلى حد ما مع وقت التشغيل $ O (| V | \ CDOT | E |) $ ، لكنني أظن أن يتم حلها بشكل أسرع. أي فكرة؟
يزعم
3. المزعوم، مشكلة أسهل ضعيفة هي العثور على مجموعة مشبعة ، وليس بالضرورة واحدة القصوى (مرة أخرى، على افتراض حدوث حالة الزواج). هل يمكننا حل هذه المشكلة بشكل أسرع من $ O (| V | \ CDOT | E |) $ ؟

---

تحرير: إليك رسم من الخوارزمية التي ذكرتها أعلاه: افترض أن حالة الزواج يحمل $ G $ . ثم، كما يقول، مع نظرية بعض الشيء يمكننا إظهار ذلك

lemma: دع $ g $ يكون الرسم البياني bipartite يرضي حالة الزواج. بعد ذلك، يتم تشبع كل نقابة من مجموعات مشبعة أيضا.

تقترح Lemma أنه يوجد هناك مجموعة كبيرة مشبعة فريدة من نوعها. يمكن أن يتم ذكر السؤال بشكل مختلف:

إعطاء عقدة $ x \ in x $ ، حدد ما إذا كان يشارك في مجموعة مشبعة أم لا .

إذا كانت الإجابة بنعم، فستشارك أيضا في الحد الأقصى للمجموعة المشبعة. يذهب خوارزمية الزائفة على النحو التالي:

1. تشغيل الخوارزمية Hopcroft-karp $ m $ يغطي $ x $ في $ o ( \ SQRT {| V |} | E |) $ الوقت. هذه المطابقة موجودة بسبب حالة الزواج.
2. لكل عقدة $ x \ in x $ ،
   • أضف مؤقتا عقدة $ X '$ إلى $ x $ ، وهو متصل بكل جار من $ x $ . استدعاء الرسم البياني نحصل على $ g_x $ .
   • لاحظ أن $ M $ هو مطابقة جزئية من $ g_x $ ما هو الحد الأقصى تقريبا (أعلى إلى حافة واحدة)؛ وبالتالي، يمكننا أن نجد أقصى قدر من المطابقة $ m_x $ for $ g_x $ من خلال العثور على مسار زيادة في < Span Class="حاوية الرياضيات"> $ g_x $ ، في $ O (| V | + | E |) $ الوقت (نفس التفاصيل كما هو الحال في Hopcroft-karp).
   • إذا $ | م | <| m_x |، $ متابعة. آخر، إذا كان $ | m |= | m_x | $ ، إضافة $ x $ إلى المجموعة التي تم إرجاعها.

يتبع التحليل من المبادئ الأولى. إذا كان هناك أي مجموعة مشبعة $ w \ subseteq x $ مع $ x \ in w $ ، أي $ | W |= | N_G (W) | $ ثم $$ | W \ Cup \ {x '\} |= | W | +1= | N_G (W) | + 1= | N_ {g_x} (W) | +1، $ حتى $ w \ cup \ {x '\} $ ينتهك شرط الزواج في $ g_x $ . وبالتالي، $ | m |= | m_x | $ . يمكننا أن تظهر بشكل مباشر أنه في حالة $ x $ لا يشارك في أي مجموعة مشبعة، ثم $ | m_x |= | m | +1 $ .

Answer 1

دعونا إصلاح أقصى استطاعيات $ m $ . دع $ z \ subseteq y $ تكون مجموعة العقد غير المتطابقة مع العقد في $ x $ وبعد يمكننا أن نرى عقدة $ x \ in x $ تنتمي إلى مجموعة مشبعة إذا وفقط إذا لم يكن هناك مسار بديل من $ x $ إلى عقدة في $ z $ ، أي مسار $ xy_1x_1 \ cdots y_kx_kz $ حيث $ (x_i، y_i) \ in m $ و $ z \ in z $ (الدليل يشبه دليل صحة الخوارزمية الخاصة بك).

حتى تتمكن من إضافة توجيهات إلى جميع الحواف في $ e $ بحيث الحواف في $ m $ لديك الاتجاه من $ x $ إلى $ y $ أثناء الحواف غير في $ m $ لديك الاتجاه من $ y $ إلى $ x $ ، ثم العقد في $ x $ غير قابل للوصول من أي عقدة في $ Z $ make the Maximal مجموعة مشبعة. يمكنك تشغيل BFS بسيطة لمعرفة العقد في $ x $ يمكن الوصول إليها من العقد في $ Z $ $ o \ left (\ sqrt {| v |} | e | \ right) $ .