خوارزمية فعالة لخفض دقيقة مع عدد محدد من القمم

Question

النظر في الرسم البياني مع القمم $ v $ والحواف $ e $ . الإصدار القياسي من مشكلة Min Cut هي العثور على قسم $ v $ في مجموعة فرعية فرعية (غير فارغة) $ C $ واستكماله $ \ bar {c} $ حتى تقلل عدد الحواف التي تسير بين $ C $ و $ \ bar {c} $ . تشتهر الخوارزميات بهذه المشكلة التي تحلها في وقت متعدد الحدود. سؤالي هو، ماذا لو أنه يحدد أحد الإضافات التي $ | C |= N $ لبعض $ n <| v | $ ؟ وهذا يعني أننا نرغب في العثور على مجموعة من $ n $ القمم مع الحد الأدنى من الحواف التي توصلها إلى بقية القمم. هل هناك خوارزميات فعالة لهذه القضية؟ أنا مهتم سواء في مسألة ما إذا كانت هذه المشكلة قابلة للحتفية رسميا في وقت متعدد الحدود (والتي أعتقد أنها) وكذلك الخوارزميات الأفضل في الممارسة العملية.

Answer 1

ل $ n=frac {| v |} 2 $ ، يطلق عليه الحد الأدنى من التهدئة، وهو NP-Hard. يوجد $ o (\ log ^ {3/2} n) $ -proximation: تقريبية polylogaritmic من الحد الأدنى من التهدئة" .

إذا كنت مهتما، فإن المشكلة العامة أكثر تقسيم في مكونات متعددة من نفس الحجم، وتسمى تقسيم الرسم البياني المتوازن. لأكثر من 2 أجزاء، لا يوجد تقريب محدود ما لم يكن P= NP: "تقسيم الرسم البياني المتوازن" (Andreev، Rakke) ، حيث لا يمكنك التحقق بكفاءة ما إذا كانت الإجابة هي 0.

إذا كانت الأجزاء ليست بالضرورة متوازنة بالضغط (لا يسمح بالاختلال الصغير)، فإن $ o (\ log n) $ خوارزمية approunmation موجودة: أقسام متوازنة من الأشجار والتطبيقات ".

---

بعض الخوارزميات (تحقق أيضا من re="nofollow noreferrer"> https://en.wikipedia.org/wiki/graph_partition< > وأقسام "المراجع" للأوراق التالية):

• البحث المحلي مع النكهات المختلفة: نبدأ مع بعض التقسيم ثم حاول تبديل القمم بين الأجزاء لتقليل القطع. على سبيل المثال نحسب "كسب" لكل قمة (تحسين إذا نقلنا إلى جزء آخر)، وقمة المبادلة بالحد الأقصى للرسب. مصلحتها هي أنه يمكنك تطبيقه بعد أي خوارزمية أخرى.

• التقسيم الطيفي (انظر على سبيل المثال نظرية الرسم البياني الطيفي التقسيم ): يستخدم Eigenvector الثاني من مصفوفة Laplacian لتقريب التقسيم (على سبيل المثال عن طريق نقل أصغر $ | الخامس | / 2 $ الإحداثيات إلى الأول جزء). يعمل بشكل جيد بشكل مدهش. ومع ذلك، لست متأكدا من أنه يمكن تكييفه مع القضية عندما تريد التناثذ غير متوازن (مثل $ 1: 2 $ بدلا من $ 1: 1 $ ).

• emigbedding الخطية: "التقسيم المتوازن الموزع عبر التضمين الخطي" . قمنا بتضمين القمم في صفيف أحادي الأبعاد مع تقليل المبلغ على جميع أزواج القمم: المسافة بينها مضروبة في وزن حافةهم. ثم نقسم هذه الصفيف فقط في قطع متتالية من الأحجام المطلوبة. لم تنجح ذلك جيدا في تجربتي.

• (ads) الورق لدينا: الرسم البياني متعدد الأبعاد متوازن التقسيم عبر نزول التدرج المتوقع "، حيث استخدمنا نزول التدرج للعثور على الحد الأدنى من التهدئة: بالنسبة لكل قمة، نقدم متغير يمثل تقريبا احتمال ينتمي الرأس إلى الجزء الأول، وتقليل خفض خفض إلى تحسين الوظيفة التربيعية. إنه منتفخ بعض الشيء في الممارسة من خلال بحث محلي صقل جيد، لكنه يعمل بشكل جيد حقا عندما يكون لديك قيود توازن متعددة.

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

هناك أيضا حلول قياسية: kahip metis . في تجربتي، كان كاهيب جيد جدا. لست متأكدا من أنها تدعم تقسيم أجزاء من الأحجام التعسفية.