2025-11-10T03:13:00.108521

The Complexity of Contracting Bipartite Graphs into Small Cycles

Krithika, Sharma, Tale
For a positive integer $\ell \geq 3$, the $C_\ell$-Contractibility problem takes as input an undirected simple graph $G$ and determines whether $G$ can be transformed into a graph isomorphic to $C_\ell$ (the induced cycle on $\ell$ vertices) using only edge contractions. Brouwer and Veldman [JGT 1987] showed that $C_4$-Contractibility is NP-complete in general graphs. It is easy to verify that $C_3$-Contractibility is polynomial-time solvable. Dabrowski and Paulusma [IPL 2017] showed that $C_{\ell}$-Contractibility is \NP-complete\ on bipartite graphs for $\ell = 6$ and posed as open problems the status of the problem when $\ell$ is 4 or 5. In this paper, we show that both $C_5$-Contractibility and $C_4$-Contractibility are NP-complete on bipartite graphs.
academic

تعقيد انكماش الرسوم البيانية ثنائية الأجزاء إلى دورات صغيرة

المعلومات الأساسية

  • معرّف الورقة: 2206.07358
  • العنوان: The Complexity of Contracting Bipartite Graphs into Small Cycles
  • المؤلفون: R. Krithika, Roohani Sharma, Prafullkumar Tale
  • التصنيف: cs.CC (نظرية التعقيد الحسابي)
  • وقت النشر/المؤتمر: ورشة العمل الدولية الـ 48 حول المفاهيم النظرية للرسوم البيانية في علوم الحاسوب (WG2022)
  • رابط الورقة: https://arxiv.org/abs/2206.07358

الملخص

بالنسبة للعدد الصحيح الموجب ℓ≥3\ell \geq 3، مسألة CℓC_\ell-Contractibility تأخذ كمدخل رسماً بيانياً بسيطاً غير موجه GG، وتحدد ما إذا كان يمكن تحويل GG من خلال عمليات انكماش الأضلاع إلى رسم بياني متطابق مع CℓC_\ell (دورة بـ ℓ\ell رأس). أثبت Brouwer و Veldman في عام 1987 أن مسألة C4C_4-Contractibility هي NP-كاملة على الرسوم البيانية العامة. يمكن حل مسألة C3C_3-Contractibility في وقت متعدد الحدود. أثبت Dabrowski و Paulusma في عام 2017 أن مسألة CℓC_\ell-Contractibility هي NP-كاملة على الرسوم البيانية ثنائية الأجزاء عندما ℓ=6\ell = 6، وطرحوا مسألة مفتوحة حول تعقيد المسألة عندما ℓ=4\ell = 4 أو 55. تثبت هذه الورقة أن مسألتي C5C_5-Contractibility و C4C_4-Contractibility هما NP-كاملتان على الرسوم البيانية ثنائية الأجزاء.

الخلفية البحثية والدافع

خلفية المسألة

  1. عمليات انكماش الرسوم البيانية: انكماش الضلع هو عملية أساسية في نظرية الرسوم البيانية، حيث يتم حذف نقطتي نهاية الضلع وإضافة رأس جديد متصل بجميع جيران النقاط الأصلية. لهذه العملية تطبيقات مهمة في التجميع والضغط والتخفيف والرسومات الحاسوبية.
  2. مسائل انكماش الدورات: مسألة CℓC_\ell-Contractibility تتطلب تحديد ما إذا كان يمكن تحويل رسم بياني معين من خلال عمليات انكماش الأضلاع إلى دورة بطول ℓ\ell. ترتبط هذه المسألة ارتباطاً وثيقاً بمعامل "الدورية" (cyclicity) للرسم البياني، والذي يُعرّف بأنه أقصى طول لدورة يمكن انكماش الرسم البياني إليها.
  3. الحالة الحالية للبحث في التعقيد:
    • C3C_3-Contractibility: قابلة للحل في وقت متعدد الحدود
    • C4C_4-Contractibility: NP-كاملة على الرسوم البيانية العامة
    • CℓC_\ell-Contractibility (ℓ≥5\ell \geq 5): NP-كاملة على الرسوم البيانية العامة
    • C6C_6-Contractibility: NP-كاملة على الرسوم البيانية ثنائية الأجزاء

دافع البحث

  1. الاكتمال النظري: تعقيد C4C_4 و C5C_5 على الرسوم البيانية ثنائية الأجزاء يمثل مسائل مفتوحة مهمة في هذا المجال
  2. تأثير القيود الهيكلية: دراسة تأثير قيود الهيكل البياني (مثل ثنائية الأجزاء) على التعقيد الحسابي
  3. توجيه تصميم الخوارزميات: توفير أساس نظري لتصميم وتحسين الخوارزميات ذات الصلة

المساهمات الأساسية

  1. النتائج النظرية الرئيسية: إثبات أن مسألتي C5C_5-Contractibility و C4C_4-Contractibility هما NP-كاملتان على الرسوم البيانية ثنائية الأجزاء
  2. الإثبات البنائي: تقديم إثبات بنائي من خلال اختزال متعدد الحدود من مسألة Positive NAE-SAT
  3. الابتكارات التقنية:
    • بالنسبة لمسألة C5C_5: تصميم طريقة بناء ثنائية الخطوات - بناء رسم بياني غير ثنائي الأجزاء HH أولاً، ثم الحصول على رسم بياني ثنائي الأجزاء GG من خلال تقسيم الأضلاع
    • بالنسبة لمسألة C4C_4: بناء مباشر لرسم بياني ثنائي الأجزاء وإثبات تكافؤه
  4. النتائج الموسعة: إثبات أن C4C_4-Contractibility هي NP-كاملة أيضاً على الرسوم البيانية الخالية من K4K_4 بقطر 2

شرح الطريقة

تعريف المهمة

المدخل: رسم بياني ثنائي الأجزاء G=(V,E)G = (V, E)المخرج: تحديد ما إذا كانت هناك سلسلة من عمليات انكماش الأضلاع التي تحول GG إلى CℓC_\ell (حيث ℓ∈{4,5}\ell \in \{4,5\}) القيود: يمكن استخدام عمليات انكماش الأضلاع فقط، لا يمكن حذف الرؤوس أو إضافة أضلاع

استراتيجية الإثبات

إثبات C5C_5-Contractibility

الخطوة الأولى: بناء رسم بياني غير ثنائي الأجزاء HH بالنظر إلى مثيل Positive NAE-SAT ψ\psi (بـ NN متغير و MM فقرة):

  1. الدورة الأساسية: إضافة 5 رؤوس Vα={α0,α1,α2,α3,α4}V_\alpha = \{\alpha_0, \alpha_1, \alpha_2, \alpha_3, \alpha_4\} تشكل دورة 5
  2. جهاز المتغيرات: لكل متغير XiX_i، إضافة دورة 5 Ci=(x0i,x1i,x2i,x3i,x4i)C_i = (x_0^i, x_1^i, x_2^i, x_3^i, x_4^i) وربطها بالدورة الأساسية
  3. جهاز الفقرات: لكل فقرة CjC_j، إضافة الرؤوس cj,bjc_j, b_j وربط الأضلاع بشكل مناسب
  4. ترميز العلاقات: ترميز العلاقات بين المتغيرات والفقرات من خلال الأضلاع x1icjx_1^i c_j و x2ibjx_2^i b_j

الخطوة الثانية: بناء رسم بياني ثنائي الأجزاء GG الحصول على رسم بياني ثنائي الأجزاء GG من خلال تقسيم مجموعة معينة من الأضلاع في HH:

  • تقسيم الضلع α0α4\alpha_0\alpha_4
  • لكل ii، تقسيم الأضلاع x0ix4i,x0iα1,x1iα2,x2iα3,x3iα4x_0^i x_4^i, x_0^i \alpha_1, x_1^i \alpha_2, x_2^i \alpha_3, x_3^i \alpha_4
  • تقسيم بعض أضلاع الاتصال بين المتغيرات والفقرات

إثبات C4C_4-Contractibility

البناء المباشر لرسم بياني ثنائي الأجزاء GG:

  1. الهيكل الأساسي: إضافة الرؤوس t,f∈Vt, f \in V و t′,f′∈V′t', f' \in V'، وربط الضلع tt′,ff′tt', ff'
  2. جهاز المتغيرات: لكل متغير XiX_i، إضافة مجموعة رؤوس وإنشاء اتصالات مناسبة
  3. جهاز الفقرات: لكل فقرة CjC_j، إضافة الرؤوس المقابلة والأضلاع
  4. الهيكل المفروض: ضمان علاقات موضع أزواج رؤوس معينة في هيكل الشاهد من خلال إضافة مجموعات رؤوس مساعدة DD و D′D'

نقاط الابتكار التقني

  1. طريقة البناء ثنائية الخطوات: بالنسبة لمسألة C5C_5، إنشاء التكافؤ على رسم بياني غير ثنائي الأجزاء أولاً، ثم التحويل إلى رسم بياني ثنائي الأجزاء، مما يتجنب تعقيد البناء المباشر على رسم بياني ثنائي الأجزاء
  2. تحليل هيكل الشاهد: إدخال مفهوم "nice witness structure"، والتحليل المنهجي لخصائص هياكل شهود C4C_4
  3. إثبات صحة الاختزال:
    • إثبات ثنائية الأجزاء للرسم البياني المُنشأ
    • إثبات تكافؤ المسألة الأصلية والرسم البياني المُنشأ
    • إنشاء تطابق ثنائي الاتجاه مع حلول مسألة SAT

إعداد التجارب

هذه الورقة عبارة عن بحث نظري بحت، ولا تتضمن تحقق تجريبي. تم الحصول على جميع النتائج من خلال الإثبات الرياضي.

نتائج التجارب

النتائج النظرية الرئيسية

النظرية 1: C5C_5-Contractibility هي NP-كاملة على الرسوم البيانية ثنائية الأجزاء النظرية 2: C4C_4-Contractibility هي NP-كاملة على الرسوم البيانية ثنائية الأجزاء النظرية 3: C4C_4-Contractibility هي NP-كاملة على الرسوم البيانية الخالية من K4K_4 بقطر 2

نقاط الإثبات الرئيسية

  1. الانتماء إلى NP: يمكن التحقق من صحة هيكل الشاهد المعطى في وقت متعدد الحدود
  2. الصعوبة NP: من خلال اختزال متعدد الحدود من مسألة Positive NAE-SAT المعروفة بأنها NP-كاملة
  3. تعقيد البناء: جميع البناءات تتم في وقت متعدد الحدود

الأعمال ذات الصلة

التطور التاريخي

  1. Brouwer و Veldman (1987): إثبات NP-اكتمال C4C_4-Contractibility على الرسوم البيانية العامة
  2. Hammack (1999, 2002): دراسة مسائل انكماش الدورات على الرسوم البيانية المستوية
  3. Dabrowski و Paulusma (2017): إثبات NP-اكتمال C6C_6-Contractibility على الرسوم البيانية ثنائية الأجزاء

المسائل ذات الصلة

  1. مسائل انكماش المسارات: PℓP_\ell-Contractibility قابلة للحل في وقت متعدد الحدود على بعض فئات الرسوم البيانية
  2. مسائل انكماش HH العامة: تحليل التعقيد على فئات رسوم بيانية مختلفة
  3. التعقيد المعاملي: دراسة مسائل الانكماش من منظور التعقيد المعاملي

الخلاصة والنقاش

الاستنتاجات الرئيسية

  1. حل كامل للمسألة المفتوحة التي طرحها Dabrowski و Paulusma
  2. إنشاء صورة تعقيد شاملة لمسائل انكماش الدورات الصغيرة على الرسوم البيانية ثنائية الأجزاء
  3. إظهار تأثير قيود الهيكل البياني على التعقيد الحسابي

القيود

  1. تعقيد البناء: الرسوم البيانية المُنشأة من الاختزال كبيرة الحجم نسبياً، قد تكون الكفاءة محدودة في التطبيقات العملية
  2. التحليل المعاملي: لم يتم تحليل المسألة من منظور التعقيد المعاملي
  3. الخوارزميات التقريبية: لم يتم مناقشة إمكانية الخوارزميات التقريبية

الاتجاهات المستقبلية

  1. فئات رسوم بيانية أخرى: دراسة التعقيد على فئات رسوم بيانية مقيدة أخرى
  2. الخوارزميات المعاملية: تطوير خوارزميات معاملية قابلة للمعالجة
  3. الخوارزميات التقريبية: تصميم خوارزميات تقريبية بنسب مضمونة
  4. مسائل الدورات الأطول: دراسة تعقيد حساب معامل الدورية للرسم البياني

التقييم المتعمق

المميزات

  1. الاكتمال النظري: حل كامل لمسألة مفتوحة مهمة، ذو قيمة نظرية عالية جداً
  2. الابتكار التقني: طريقة البناء ثنائية الخطوات ومفهوم nice witness structure لهما أهمية منهجية
  3. الإثبات الدقيق: جميع النظريات لها إثباتات رياضية كاملة، المنطق واضح
  4. جودة الكتابة: الورقة منظمة بشكل جيد، التعبير واضح، الأشكال والجداول توضيحية فعالة

أوجه القصور

  1. قيود الجدوى العملية: نتائج نظرية بحتة، تفتقر إلى تنفيذ الخوارزميات وتحليل الأداء
  2. تعقيد البناء: بناء الاختزال معقد نسبياً، عتبة الفهم عالية
  3. القابلية للتوسع: لم يتم مناقشة تأثير النتائج على المسائل ذات الصلة بشكل كافٍ

التأثير

  1. المساهمة الأكاديمية: ملء فجوة مهمة في نظرية التعقيد الحسابي
  2. القيمة المنهجية: توفير تقنيات يمكن استخدامها في دراسة مسائل مشابهة
  3. البحث اللاحق: وضع أساس لمزيد من البحث في المجالات ذات الصلة

السيناريوهات المناسبة

  1. البحث النظري: بحث نظرية الرسوم البيانية والتعقيد الحسابي
  2. تصميم الخوارزميات: توفير توجيه نظري للتعقيد لتصميم الخوارزميات ذات الصلة
  3. التطبيقات التعليمية: بمثابة حالة كلاسيكية لإثبات NP-اكتمال

المراجع

تستشهد الورقة بـ 29 مرجعاً ذا صلة، تغطي:

  • الأعمال المبكرة في مسائل انكماش الرسوم البيانية
  • أساسيات نظرية التعقيد الحسابي
  • نتائج NP-اكتمال ذات صلة
  • نظرية الرسوم البيانية الأساسية

تشمل المراجع الرئيسية Brouwer و Veldman (1987)، Dabrowski و Paulusma (2017)، Garey و Johnson (1979) وغيرها من الأعمال الكلاسيكية.