كيف تثبت العثور على مسارين من حواف K على الأقل هو NP-Hard؟

Question

دع $ g= (v، e) $ رسم بياني غير مريض وغير مريض ومتصل. نظرا لشخصين البدء $ s_1 $ و $ s_2 $ واثنين من رؤوس النهاية $ t_1 $ and $ t_2 $ هل هناك مسار من $ s_1 $ إلى $ T_1 $ و $ s_2 $ إلى $ t_2 $ بحيث يكون أقرب عدد من الحواف بين المسارين على الأقل $ k $ ؟ اثنين من المسارات هي $ K $ إغلاق إذا كان الحد الأدنى من أقصر المسافات بين أي قمة على المسار الأول إلى أي قمة على المسار الثاني هو $ K $ .

كنت أفكر في تقليل 3SAT والسماح للمسار الأول تمثيل المتغيرات والمسار الثاني يمثل البنود، لكنني غير متأكد من أين أذهب من هناك.

Answer 1

يمكنك تقليل من 3SAT.

الرسم البياني لديه جزأين. جزء واحد هو الجزء "المتغير". لكل من المتغيرات $ v_1، \ ldots، v_n $ هناك نوعان من ثلاث رؤوس $ v_i ^ +، v_i ^ - ، v_i $ ، وهذا الجزء يتكون من الحواف التالية، ل $ i \ in [n] $ :

$$ (v_ {i-1}، v_i ^ +)، (v_ {i-1}، v_i ^ -)، (v_i ^ +، v_i)، ( v_i ^ -، v_i) $

هنا $ v_0 $ هي قمة جديدة، مع تحديدها مع $ S_1 $ ، و $ V_N $ تم تحديدها مع $ t_1 $ .

الجزء الثاني هو جزء "البند". لكل من البنود $ c_1، \ ldots، c_m $ هناك أربعة رؤوس $ w_j ^ 1، w_j ^ 2، w_j ^ 2 ^ 3، W_J $ ، متصلة كثيرا كما كان من قبل، مع $ s_2 $ and $ t_2 $ .

نحن نتصل $ v_i ^ b $ مع $ w_j ^ r $ عبر مسار طول < SPAN CLASS="حاوية الرياضيات"> $ K $ (لبعضها كبير بما يكفي $ K $ ) إذا كانت $ v_i ^ b $ (إما $ v_i $ أو $ \ overline {v_i} $ < / span>، وفقا ل $ B $ ) هو عكس من $ J $ "الحرف الحرفي $ c_j $ .

أيضا، نأخذ جميع نقاط نفذات هذه المسارات، وتوصيلها جميعا (مما يجعلها في زمرة).

يمكننا التفكير في $ (s_1، t_1) $ -path كعناية للحقيقة، و $ (S_2، T_2) $ -Path كما هو تحديد حرفية راضية في كل جملة. الحد الأدنى للمسافة أكثر من $ K $ إذا كان هذا هو في الواقع الحالة، وفقط $ K $ خلاف ذلك وبعد

تحتاج أيضا إلى التحقق من عدم وجود نقطة للمسارات لعبور بين الأجزاء. إذا تعبر إحدى المسارات فقط، فستكون المسارين قريبة من بعضها البعض (في بعض المسافة المستمرة، والتي لن تكون كبيرة بما يكفي $ K $ ستكون أصغر من $ K $ ) مباشرة بعد المعبر. إذا كان كلاهما عبور، فسوف يضمن زمرة منتصف نقطة أن تكون في المسافة على الأقل 1.