كيفية إثبات NP-اكتمال أطول الطريق بين اثنين من القمم الاعتماد هاميلتون NP-Hard المشكلة

Question

لدي هذا السؤال:لدي الرسم البياني صليات ز(V, E) (حيث V = مجموعة من القمم ، هـ = مجموعة من حواف).النظر في المسار الحد الأقصى بين اثنين من القمم s و t:

LPATH = {⟨G,s,t,k⟩|There is in G a simple path as long as at least k from s to t}

بسيطة المسار هو المسار دون أي تكرار vertice ، أيكل vertice يمكن زيارتها مرة واحدة فقط.طول مسار معين من حواف التي يتألف منها.

كيف يمكنني إظهار أن LPATH هو NP-Complete المشكلة باستخدام هاميلتون مسار المشكلة كما NP-Hard المشكلة كما ذكرتها ؟

Answer 1

مرحبا بكم في الموقع!السماح $G = (V, E)$ يكون صليات الرسم البياني.إذا $G$ هو هاميلتونايان ، ثم هناك دورة بسيطة $C$ في $G$ تحتوي كل قمة ، أيطول $C$ هو $|V|$.لاحظ أنه إذا قمت بحذف أي حافة $فولكس فاجن$ من $C$, ، كنت في نهاية المطاف مع مسار طول $|V| - 1$ بين $v$ و $w$.على العكس من ذلك ، إذا كنت تجد مسار بسيط $P$ من طول $|V| - 1$ بين اثنين من القمم $v, w$ متصلة بواسطة الحافة ، يمكنك إضافة حافة $فولكس فاجن$ إلى $P$ للحصول على هاميلتونايان دورة (كما $P$ لا يمكن أن تحتوي على $فولكس فاجن$ نظرا إلى كونها بسيطة المسار).نلاحظ أيضا أن اختيار $v$ و $w$ تعسفيا طالما أنها ترتبط بها الحافة.

حتى نتمكن من الحصول على التخفيض التالية:بدءا من الرسم البياني $G = (V, E)$, واختيار بعض الحافة $فولكس فاجن \في E$ وحذف الحصول على الرسم البياني $G' = (V, E \setminus \{فولكس فاجن\})$.استخدام الملاحظات ، ويترتب على ذلك $G'$ وقد مسار $P$ بين $v$ و $w$ من طول $|V| - 1$ إذا و فقط إذا كان إضافة $فولكس فاجن$ إلى $P$ ينتج هاميلتونايان دورة في الرسم البياني الأصلي $G$.كما $G'$ يمكن حسابها من $G$ في وقت متعدد الحدود ، لدينا متعدد الحدود الحد $\mathrm{هاميلتونايان دورة} \leq_\mathsf{P} \mathrm{الطريق الطويل}$, ، مما يدل على أن المشكلة $\mathsf{NP}$-بجد (لأن $\mathrm{هاميلتونايان دورة}$ هو $\mathsf{NP}$-من الصعب بالفعل).

لإظهار أن $\mathrm{الطريق الطويل}$ هو في $\mathsf{NP}$ نلاحظ أن مسار في الرسم البياني يمكن أن تكون كفاءة ترميز قائمة من أطرافها والتحقق من أن سلسلة في الواقع بترميز الطريق في الرسم البياني ومن ثم عد عدد من حواف لتحديد ما إذا كان هو طويل بما فيه الكفاية يمكن القيام به في وقت متعدد الحدود.

ومن هنا نجد أن $\mathrm{الطريق الطويل}$ هو $\mathsf{NP}$-كاملة.