التكافؤ بين Min Uncut و Min-CSP_XOR

Question

في هذه الورقة

agarwal، amit، et al. "O (تسجيل الدخول n) خوارزميات التقريب لتقويم الحد من حذف Min Uncut و Min 2CNF ومشكلات قطع موجهة". وقائع ندوة ACM السنوية الثلاثين في نظرية الحوسبة. 2005.

agarwal et al. الادعاء بأن المشكلتين التاليين تعادلان.

النظر في المتغيرات المنطقية $ b_1، \ dots، b_n $ ومجموعة من القيود من النموذج $ b_i \ oplus B_J= 0 $ و $ b_i \ oplus b_j= 1 $ . الهدف هو تقليل عدد القيود غير الراضية.

و

بالنظر إلى الرسم البياني $ g= (v، e) $ ابحث عن قطع يقلل من عدد الحواف غير الصغر.

إذا كانت القيود فقط من النموذج $ b_i \ oplus b_j= 1 دولار ، فإن المعادلة واضحة. ومع ذلك، إذا كنا نعتبر أيضا قيودا من النموذج $ b_i \ oplus b_j= 0 $ ، يبدو الصيغة الأولى أكثر عمومية بالنسبة لي.

كيف هي هذه المعادل؟

Answer 1

لنفترض أننا نحتاج إلى مجموعة من قيود النموذج $ b_i \ oplus b_j= c $ . نحن نبني رسم بياني مع قمة واحدة مقابلة لكل $ b_i $ . لكل عائق من النموذج $ b_i \ oplus b_j= 1 $ ، نضيف حافة $ \ {i، j \ } $ . لكل عائق من النموذج $ b_i \ oplus b_j= 0 $ ، نقوم بإضافة قمة الرأس $ x $ ، واثنين من الحواف $ \ {i، x \}، \ {j، x \} $ .

يمكننا التفكير في قطع كقسمة من القمم إلى قسمين. لقيود النموذج $ b_i \ oplus b_j= 1 دولار ، القيد غير راضي IFF $ I، J $ < / SPAN> تنتمي إلى نفس الجزء IFF $ \ {i، j \} $ هو غير مصقول. للحصول على قيد من النموذج $ b_i \ oplus b_j= 0 $ ، هناك حالتان:

• إذا كان القيد غير راض، ثم $ i، j $ تنتمي إلى أجزاء مختلفة، وبالضبط واحدة من الحواف $ \ {i، x \}، \ {j، x \} $ هو Uncut.

• إذا كان القيد غير مرضي غير مرضي، ثم $ i، j $ تنتمي إلى نفس الجزء، وكذلك (اعتمادا على موقع $ x $ ) إما الصفر أو اثنين من الحواف $ \ {i، x \}، \ {j، x \} $ < / span> هي تقطيعه. نظرا لأننا نهدف إلى تقليل عدد الحواف غير القريبة، فيمكننا أن نفترض أن الصفر غير مصقول.

في المجموع، وعدد القيود غير الراضية هو نفس عدد الحواف غير الصغرية.