2025-11-13T16:28:10.775883

A CSP approach to Graph Sandwich Problems

Bodirsky, Guzmán-Pro
The \emph{Sandwich Problem} (SP) for a graph class $\calC$ is the following computational problem. The input is a pair of graphs $(V,E_1)$ and $(V,E_2)$ where $E_1\subseteq E_2$, and the task is to decide whether there is an edge set $E$ where $E_1\subseteq E \subseteq E_2$ such that the graph $(V,E)$ belongs to $\calC$. In this paper we show that many SPs correspond to the constraint satisfaction problem (CSP) of an infinite $2$-edge-coloured graph $H$. We then notice that several known complexity results for SPs also follow from general complexity classifications of infinite-domain CSPs, suggesting a fruitful application of the theory of CSPs to complexity classifications of SPs. We strengthen this evidence by using basic tools from constraint satisfaction theory to propose new complexity results of the SP for several graph classes including line graphs of multigraphs, line graphs of bipartite multigraphs, $K_k$-free perfect graphs, and classes described by forbidding finitely many induced subgraphs, such as $\{I_4,P_4\}$-free graphs, settling an open problem of Alvarado, Dantas, and Rautenbach (2019). We also construct a graph sandwich problem which is in coNP, but neither in P nor coNP-complete (unless P = coNP).
academic

نهج CSP لمسائل شطيرة الرسم البياني

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

  • معرّف الورقة: 2510.09128
  • العنوان: A CSP approach to Graph Sandwich Problems
  • المؤلفون: Manuel Bodirsky, Santiago Guzmán-Pro (جامعة TU Dresden)
  • التصنيف: cs.DM (الرياضيات المنفصلة)، cs.CC (التعقيد الحسابي)، math.CO (الرياضيات التوافقية)
  • تاريخ النشر: 13 أكتوبر 2025
  • رابط الورقة: https://arxiv.org/abs/2510.09128

الملخص

مسألة شطيرة الرسم البياني (Graph Sandwich Problem, SP) هي مسألة حسابية مهمة في نظرية الرسوم البيانية. بالنسبة لفئة الرسوم البيانية C\mathcal{C}، تُعرّف مسألة الشطيرة كما يلي: بمعطيات رسمان بيانيان (V,E1)(V,E_1) و (V,E2)(V,E_2) حيث E1⊆E2E_1 \subseteq E_2، حدّد ما إذا كانت هناك مجموعة أضلاع EE بحيث E1⊆E⊆E2E_1 \subseteq E \subseteq E_2 والرسم البياني (V,E)(V,E) ينتمي إلى C\mathcal{C}. تثبت هذه الورقة أن العديد من مسائل الشطيرة تكافئ مسائل إرضاء القيود (CSP) للرسوم البيانية ذات الألوان الثنائية للأضلاع اللانهائية HH، وتستخدم نظرية CSP لتقديم نتائج تعقيد جديدة لعدة فئات رسوم بيانية، بما في ذلك الرسوم البيانية الخطية للرسوم البيانية متعددة الأضلاع، والرسوم البيانية الخطية للرسوم البيانية ثنائية الأجزاء متعددة الأضلاع، والرسوم البيانية الكاملة الخالية من KkK_k، مما يحل المسائل المفتوحة التي طرحها Alvarado وآخرون (2019).

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

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

  1. الأهمية النظرية: مسألة شطيرة الرسم البياني هي مسألة كلاسيكية في نظرية الرسوم البيانية، قدمها Golumbic وآخرون عام 1995، وهي تعميم طبيعي لمسائل التعرف على الرسوم البيانية
  2. التعقيد الحسابي: مسائل الشطيرة صعبة على الأقل مثل مسائل التعرف المقابلة، وتصنيف تعقيدها موضوع مهم في نظرية الخوارزميات الرسومية
  3. المسائل المفتوحة: يبقى تعقيد مسألة شطيرة الرسوم البيانية الكاملة غير محدد، وتُعتبر من أهم المسائل المفتوحة في هذا المجال

قيود الطرق الموجودة

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

الدافع البحثي

تهدف هذه الورقة إلى إنشاء ارتباط بين مسائل شطيرة الرسم البياني ومسائل إرضاء القيود، واستخدام أدوات نظرية CSP الناضجة لتوفير إطار تحليل موحد لمسائل الشطيرة.

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

  1. إنشاء إطار نظري: إثبات أن مسائل الشطيرة لفئات الرسوم البيانية التي تستوفي شروطاً معينة تكافئ CSP للرسوم البيانية ذات الألوان الثنائية للأضلاع
  2. نتائج تعقيد جديدة: توفير تصنيفات تعقيد جديدة لعدة فئات رسوم بيانية، بما في ذلك:
    • نسخ الرسوم البيانية الخطية متعددة الأضلاع وثنائية الأجزاء
    • الرسوم البيانية الكاملة الخالية من KkK_k
    • الرسوم البيانية الخالية من {I4,P4}\{I_4,P_4\} وغيرها
  3. حل المسائل المفتوحة: حل المسألة المفتوحة التي طرحها Alvarado وآخرون (2019) بشأن مسألة شطيرة الرسوم البيانية الخالية من {I4,P4}\{I_4,P_4\}
  4. نتائج عدم الثنائية: بناء مسائل شطيرة رسوم بيانية وسيطة في coNP، مما يثبت عدم تفاهة تصنيف التعقيد

شرح الطريقة

تعريف المهمة

مسألة شطيرة الرسم البياني (SP): بمعطيات فئة رسوم بيانية C\mathcal{C} والمدخلات (V,E1,E2)(V,E_1,E_2) حيث E1⊆E2E_1 \subseteq E_2، حدّد ما إذا كانت هناك EE بحيث E1⊆E⊆E2E_1 \subseteq E \subseteq E_2 و (V,E)∈C(V,E) \in \mathcal{C}.

التعبير المكافئ: المدخلات عبارة عن ثلاثية (V,E,N)(V,E,N)، حيث EE هي مجموعة الأضلاع الإجبارية، و NN هي مجموعة الأضلاع المحظورة، حدّد ما إذا كانت هناك رسم بياني (V,E′)∈C(V,E') \in \mathcal{C} بحيث E⊆E′E \subseteq E' و E′∩N=∅E' \cap N = \emptyset.

إطار العمل النظري الأساسي

الرسوم البيانية ذات الألوان الثنائية للأضلاع و CSP

  • الرسم البياني ذو الألوان الثنائية للأضلاع: ثلاثية (V,B,R)(V,B,R)، حيث BB هي مجموعة الأضلاع الزرقاء، و RR هي مجموعة الأضلاع الحمراء، و B∩R=∅B \cap R = \emptyset
  • التشاكل: تعيين الرؤوس الذي يحافظ على علاقات الجوار والألوان
  • CSP(H)(H): فئة جميع الرسوم البيانية ذات الألوان الثنائية للأضلاع المحدودة التي يمكن تعيينها بشكل متشاكل إلى HH

نظرية التوصيف الرئيسية

الاقتراح 3: بالنسبة لفئة رسوم بيانية C\mathcal{C}، ما يلي متكافئ:

  1. C\mathcal{C} وراثية، لها خاصية الدمج المشترك وتُغلق تحت التمدد المقسم
  2. يوجد رسم بياني ذو ألوان ثنائية للأضلاع (V,R,B)(V,R,B) بحيث CSP(V,R,B)=SP(C)(V,R,B) = \text{SP}(\mathcal{C})
  3. يوجد رسم بياني HH بحيث SP(C)=CSP(H∗)=injCSP(H∗)(\mathcal{C}) = \text{CSP}(H^*) = \text{injCSP}(H^*)

حيث H∗H^* يشير إلى الرسم البياني الكامل ذو الألوان الثنائية للأضلاع، مع الأضلاع الزرقاء E(H)E(H) والأضلاع الحمراء N(H)N(H).

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

1. البناء الإيجابي الأولي (Primitive Positive Constructions)

استخدام بناء pp لإنشاء علاقات اختزال بين مسائل CSP، وهذا يتوافق مع اختزالات gadget في نظرية الرسوم البيانية.

2. نظرية الرسوم البيانية العامة

بالنسبة لفئة رسوم بيانية وراثية C\mathcal{C}، إذا كان هناك رسم بياني عام HH (أي Age(H)=C(H) = \mathcal{C})، فإن SP(C)=CSP(H∗)(\mathcal{C}) = \text{CSP}(H^*).

3. الإغلاق تحت التمدد المقسم

  • التمدد: إضافة twins (رؤوس بنفس الجوار)
  • التمدد المشترك: إضافة co-twins (رؤوس بنفس الجوار باستثناء بعضها البعض)
  • التمدد المقسم: تمدد أو تمدد مشترك بناءً على تقسيم الرؤوس (I,C)(I,C)

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

التحقق النظري

هذه الورقة عمل نظرية بشكل أساسي، وتتحقق من فعالية الطريقة بالطرق التالية:

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

أدوات التحليل

  • برامج Datalog: حل بعض مسائل CSP القابلة للحل في وقت متعدد الحدود
  • اختزالات MMSNP: اختزال مسائل CSP ذات المجال اللانهائي إلى مسائل ذات مجال محدود
  • الطريقة الجبرية: استخدام تعدد الأشكال لتحليل تعقيد CSP

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

نتائج التعقيد الرئيسية

1. ما يتعلق بالرسوم البيانية الخطية

  • النظرية: مسألة شطيرة الرسوم البيانية الخطية متعددة الأضلاع هي NP-complete
  • النظرية: مسألة شطيرة الرسوم البيانية الخطية ثنائية الأجزاء متعددة الأضلاع هي NP-complete

2. فئات الرسوم البيانية المحظورة

  • النتيجة 18: بالنسبة لـ k≥4k \geq 4، مسائل الشطيرة للرسوم البيانية الخالية من {P4,Kk}\{P_4,K_k\} والخالية من {P4,Ik}\{P_4,I_k\} والرسوم البيانية الكاملة الخالية من KkK_k كلها NP-complete
  • النظرية 17: لتكن FF مجموعة رسوم بيانية غير محددة بالكامل بحيث تكون الرسوم البيانية الخالية من FF كاملة، فإن مسألة شطيرة الرسوم البيانية الخالية من (F∪{Kk})(F \cup \{K_k\}) هي NP-hard بالنسبة لـ k≥4k \geq 4

3. المسارات المحظورة

  • النظرية 20: بالنسبة لـ n,k≥4n,k \geq 4، مسألة شطيرة الرسوم البيانية الخالية من {Pn,Kk}\{P_n,K_k\} هي NP-complete

تصنيف التعقيد الخوارزمي

الحالات القابلة للحل في وقت متعدد الحدود

  • الرسوم البيانية المقسمة: من خلال اختزال 2-SAT
  • الرسوم البيانية الحدية: باستخدام تعدد أشكال متماثل كامل
  • الرسوم البيانية متعددة الأجزاء الكاملة: حل برنامج Datalog

حالات NP-complete

  • الرسوم البيانية المقارنة: من خلال اختزال CSP للأوامر الجزئية العشوائية
  • الرسوم البيانية الترتيبية: من خلال اختزال مسألة betweenness
  • الرسوم البيانية المقسمة المعممة: الرسوم البيانية (p,q)(p,q)-المقسمة عندما p+q>2p+q > 2

نتائج عدم الثنائية

النظرية 21: إذا كانت P ≠\neq coNP، فإنه يوجد فئة رسوم بيانية C\mathcal{C} بحيث تكون SP(C)(\mathcal{C}) وسيطة في coNP.

يعتمد البناء على تكييف نظرية Ladner، مما يثبت أن تعقيد مسائل شطيرة الرسوم البيانية يتجاوز ثنائية P مقابل NP.

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

أبحاث مسائل شطيرة الرسوم البيانية

  • Golumbic وآخرون (1995): أول دراسة منهجية لمسائل شطيرة الرسوم البيانية
  • الأعمال اللاحقة: تصنيفات التعقيد لفئات رسوم بيانية محددة
  • المسائل المفتوحة: تعقيد مسألة شطيرة الرسوم البيانية الكاملة لم يُحدد بعد

نظرية إرضاء القيود

  • نظرية Schaefer: ثنائية CSP للمجال البولياني
  • نظرية Hell-Nešetřil: تصنيف مسائل تشاكل الرسوم البيانية
  • ثنائية المجال المحدود: نتائج Bulatov و Zhuk الرائدة
  • CSP ذات المجال اللانهائي: تصنيف الحالات الخاصة مثل CSP الزمنية

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

تنشئ هذه الورقة للمرة الأولى ارتباطاً منهجياً بين مسائل شطيرة الرسوم البيانية و CSP ذات المجال اللانهائي، مما يوفر منظوراً جديداً للتقاطع بين المجالين.

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

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

  1. التوحيد النظري: يمكن تحليل مسائل شطيرة الرسوم البيانية بشكل منهجي باستخدام نظرية CSP
  2. فعالية الطريقة: يمكن لأدوات CSP تبسيط إثباتات التعقيد واكتشاف نتائج جديدة
  3. ثراء التعقيد: تعرض مسائل الشطيرة طيفاً كاملاً من التعقيد من P إلى coNP-intermediate

القيود

  1. نطاق التطبيق: ينطبق فقط على فئات الرسوم البيانية التي تستوفي شروطاً معينة (وراثية، JEP، إغلاق تحت التمدد المقسم)
  2. مسألة الرسوم البيانية الكاملة: أهم مسألة مفتوحة (مسألة شطيرة الرسوم البيانية الكاملة) لا تزال دون حل
  3. البناء: تفتقر بعض النتائج الوجودية إلى خوارزميات بناء فعالة

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

  1. الهياكل ω-المصنفة: دراسة مسائل الشطيرة لفئات الرسوم البيانية ω-المصنفة
  2. مسألة الرسوم البيانية الكاملة: البحث عن حل لمسألة شطيرة الرسوم البيانية الكاملة
  3. القابلية للقرار: دراسة قابلية القرار لتعقيد التصنيف عند إعطاء مجموعة من الرسوم البيانية المحظورة
  4. NP-intermediate: البحث عن مسائل شطيرة رسوم بيانية وسيطة في NP

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

المزايا

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

أوجه القصور

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

التأثير

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

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

هذه الطريقة مناسبة بشكل خاص لـ:

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

المراجع

تستشهد الورقة بـ 61 مرجعاً ذا صلة، تشمل بشكل أساسي:

  • الأعمال الأساسية لمسائل شطيرة الرسوم البيانية 38
  • النتائج الأساسية لنظرية CSP 20,59,60
  • نتائج تصنيف CSP ذات المجال اللانهائي 10,11,46
  • النتائج الهيكلية في نظرية الرسوم البيانية 22,23,37,47

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