هل شاهد أي شخص مشكلة رسم بياني NP مثل هذا من قبل؟

Question

لدي مشكلة في الرسم البياني التالي:

1. المدخلات: أعداد صحيحة إيجابية K و L، الرسم البياني غير المعالج G
2. يجب أن أختار قمة k من هذا الرسم البياني
3. في المسار بين كل زوج من القمم K المختارة هناك يجب أن يكون هناك قمة L على الأقل، وأنا.ه.يجب أن يكون هناك "مساحة بين" كل اثنين من القمم المختارة مصنوعة من القصير الأقل.

قد لا يكون ذلك ممكنا في الدورة التدريبية مثيل معين للمشكلة، ثم لا بد لي من التحقق من ذلك.أنا متأكد تماما من أن هذه المشكلة هي NP أو حتى NP-Complete، لأنه يتعلق الأمر بمسارات مع قيود الطول.هل سبق لك أن قابلت مشكلة مماثلة؟هل لديك فكرة عن كيفية تقليلها إلى مشكلة أكثر شهرة، ربما NP، ه.ز.غطاء رأس أو تلوين الرسم البياني؟

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

Answer 1

يعرف هذا باسم المسافة- $ D $ مجموعة مستقلة، أي، كنت تبحث عن مجموعة مستقلة من الحجم $ k $ حيث توجد المسافة بين كل عنصرين في الحل على الأقل $ D $ .

المشكلة هي np-complete حتى على الرسوم البيانية المستوية وفقا ل [1]، لكنني لا أعرف عن تعقيدها على الشبكات الجزئية.

فيما يتعلق بالتخفيضات، ربما يمكنك أن تأخذ $ d $ 'th قوة الرسم البياني والعثور على (المسافة-1) مجموعة مستقلة في ذلك. المطالبة هي أن أي حل هنا مسافة - $ D $ مجموعة مستقلة في الأصل، ولكن عليك التحقق من ذلك.

---

[1] ETO، HIROSHI، FENGRUI GUO، وأياجي ميانو. "المسافة - $ D $ مشاكل المحددة المستقلة الرسوم البيانية الثمانية والكرات." مجلة تحسين الحركة 27، لا. 1 (2014): 88-99.

Answer 2

في الحالة الخاصة حيث $ l= 1 $ ، هذا هو الحد الأقصى لمشكلة تعيين مستقلة ، وهو NP-Hard على الرسوم البيانية العامة. لذلك، مشكلتك هي NP-Hard على الرسوم البيانية العامة أيضا.

يمكنك محاولة الأمل في خوارزمية محددة لفئة الرسوم البيانية التي لديك (أعتقد أن الحد الأقصى المستقلة المحددة يمكن حسابها بكفاءة في الرسوم البيانية الحليين ، والرسوم البيانية الشبكة هي bipartite، حتى تتمكن من محاولة تعميم تلك الخوارزمية)، أو يمكنك محاولة استخدام خوارزمية قياسية لتحقيق أقصى مجموعة / زمرة مستقلة، أو يمكنك محاولة استخدام SAT حلال يجب أن يكون من السهل صياغة هذا كمثيل Maxsat: لديك جملة لكل زوج من القمم المسافة عن بعد $ l + 1 $ (أو أقل)، و أنت تسأل SAT Solver لتقليل عدد المتغيرات المحددة إلى TRUE.

Answer 3

يبدو أن

يشبه التحقق مما إذا كانت هناك مجموعة فرعية من G من G.أعني ما إذا كانت جميع القمم K ملونة مع نفس اللون، فإنهم يرضيون حالتك.

منذ تلوين الرسم البياني في NP-Complete يمكنك التحقق من محلول معين في وقت متعدد الحدود.

لذلك ربما، ربما تكون هذه الإجابة الأولى الأولى، يجب عليك

1 - تحقق مما إذا كان الرسم البياني الخاص بك هو L- قابلة للتصوير

2 - ابحث عن لون مع مجموعة من القمم K