إثبات العثور على مسارات مفككة K من المسارات المحددة في الرسم البياني الموجه هو NP-Complete

Question

المشكلة: إعطاء مسارات N في الرسم البياني الموجه G (V، E) و ENTEGER K، ومعرفة مسارات K فيما بينها بحيث لا يمر اثنان منهم من خلال عقدة شائعة.

تثبت أن المشكلة المعينة هي في NP-Complete.

كنت قادرا على إثبات أن المشكلة في NP.تلميح هو أننا نحتاج إلى التوصل إلى الحد الأقصى للوقت متعدد الحدود من مشكلة المجموعة المستقلة في هذه المشكلة تثبت أنه في NP-Hard.

Answer 1

عضوية مشكلتك في $ \ mathsf {np} $ هي تافهة. لإثبات أنه أيضا $ \ mathsf {np} $ النظر في مثيل (إصدار القرار من) مجموعة مستقلة تتكون من الرسم البياني $ g= (v، e) $ مع $ | v |= n $ وعدد صحيح $ K $ .

بناء الرسم البياني $ h= (v '، e') $ حيث $ v '= v \ cup \ {x_ u، v} \،: \، (u، v) \ in e \} $ و $ e '= v' \ times v '$ < / span>.

مقابل كل $ u \ in v دع $ v_1، v_2، \ dots، v_h $ $ u $ في $ g $ وحدد المسار $ p_u=lange u، x_ {u، v_1}، x_ {u، v_2}، \ dots، x_ {u، v_h} \ rangle $ في $ h $ . دع $ \ mathcal {p}={p_u \،: \ u \ u \ in v \} $ .

هناك مجموعة مستقلة من الحجم على الأكثر $ K $ في $ g $ ، إذا و فقط إذا كان هناك مجموعة فرعية $ \ mathcal {p} '$ مع $ | \ mathcal {p}' | \ Le K $ بحيث المسارات في $ \ mathcal {p} '$ disfoint verfex.

أكثر دقة، إذا $ S $ هي مجموعة مستقلة من $ g $ ، ثم $ \ {p_u \،: \، u \ in s \} $ هي عبارة عن مجموعة من مسارات Vertex-Disfoint الزوجية في $ h $ ، وإذا كان $ \ mathcal {p} '$ هو مجموعة من مسارات Vertex-Disfoint الزوجية في $ h $ ، ثم $ \ {u \،: \، p_u \ in \ mathcal {p} '\} $ هي مجموعة مستقلة من < Span Class="حاوية الرياضيات"> $ G $ .