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 (সমন্বয় গণিত)
  • প্রকাশনার সময়: ২০২৫ সালের ১৩ অক্টোবর
  • পেপার লিঙ্ক: 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} এ অন্তর্ভুক্ত থাকে। এই পেপারটি প্রমাণ করে যে অনেক স্যান্ডউইচ সমস্যা অসীম ২-প্রান্ত রঙিন গ্রাফ HH এর সীমাবদ্ধতা সন্তুষ্টি সমস্যা (CSP) এর সমতুল্য, এবং CSP তত্ত্ব ব্যবহার করে একাধিক গ্রাফ শ্রেণীর স্যান্ডউইচ সমস্যার জন্য নতুন জটিলতার ফলাফল প্রদান করে, যার মধ্যে রয়েছে বহুগ্রাফের লাইন গ্রাফ, দ্বিপক্ষীয় বহুগ্রাফের লাইন গ্রাফ, KkK_k-মুক্ত নিখুঁত গ্রাফ ইত্যাদি, এবং Alvarado এবং অন্যদের (২০১৯) দ্বারা উত্থাপিত উন্মুক্ত সমস্যা সমাধান করে।

গবেষণার পটভূমি এবং প্রেরণা

সমস্যার গুরুত্ব

  1. তাত্ত্বিক তাৎপর্য: গ্রাফ স্যান্ডউইচ সমস্যা গ্রাফ তত্ত্বের একটি ক্লাসিক সমস্যা, যা Golumbic এবং অন্যদের দ্বারা ১৯৯৫ সালে প্রবর্তিত হয়েছিল, এবং এটি গ্রাফ স্বীকৃতি সমস্যার একটি প্রাকৃতিক সম্প্রসারণ
  2. গণনামূলক জটিলতা: স্যান্ডউইচ সমস্যা অন্তত সংশ্লিষ্ট গ্রাফ স্বীকৃতি সমস্যার মতোই কঠিন, এবং এর জটিলতা শ্রেণীবিভাগ অ্যালগরিদমিক গ্রাফ তত্ত্বের একটি গুরুত্বপূর্ণ বিষয়
  3. উন্মুক্ত সমস্যা: নিখুঁত গ্রাফের স্যান্ডউইচ সমস্যার জটিলতা এখনও নির্ধারিত হয়নি, এবং এটি এই ক্ষেত্রের সবচেয়ে গুরুত্বপূর্ণ উন্মুক্ত সমস্যাগুলির মধ্যে একটি হিসাবে বিবেচিত হয়

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

  1. একীভূত কাঠামোর অভাব: বিদ্যমান গবেষণা প্রধানত নির্দিষ্ট গ্রাফ শ্রেণীর জন্য বিশেষায়িত কৌশল ব্যবহার করে, সর্বজনীন বিশ্লেষণ পদ্ধতির অভাব রয়েছে
  2. প্রমাণের জটিলতা: ঐতিহ্যবাহী কঠোরতার প্রমাণ সাধারণত জটিল হ্রাস নির্মাণের প্রয়োজন হয়
  3. সীমিত তাত্ত্বিক সরঞ্জাম: স্যান্ডউইচ সমস্যার জটিলতা বিশ্লেষণের জন্য পদ্ধতিগত তাত্ত্বিক সরঞ্জামের অভাব রয়েছে

গবেষণার প্রেরণা

এই পেপারটি গ্রাফ স্যান্ডউইচ সমস্যা এবং সীমাবদ্ধতা সন্তুষ্টি সমস্যার মধ্যে সংযোগ স্থাপনের লক্ষ্য রাখে, এবং স্যান্ডউইচ সমস্যার জন্য একটি একীভূত বিশ্লেষণ কাঠামো প্রদান করতে CSP তত্ত্বের পরিপক্ক সরঞ্জাম ব্যবহার করে।

মূল অবদান

  1. তাত্ত্বিক কাঠামো প্রতিষ্ঠা: প্রমাণ করে যে নির্দিষ্ট শর্ত পূরণকারী গ্রাফ শ্রেণীর স্যান্ডউইচ সমস্যা ২-প্রান্ত রঙিন গ্রাফের CSP এর সমতুল্য
  2. জটিলতার নতুন ফলাফল: একাধিক গ্রাফ শ্রেণীর জন্য নতুন জটিলতা শ্রেণীবিভাগ প্রদান করে, যার মধ্যে রয়েছে:
    • লাইন গ্রাফের বহুগ্রাফ এবং দ্বিপক্ষীয় বহুগ্রাফ সংস্করণ
    • KkK_k-মুক্ত নিখুঁত গ্রাফ
    • {I4,P4}\{I_4,P_4\}-মুক্ত গ্রাফ ইত্যাদি
  3. উন্মুক্ত সমস্যা সমাধান: Alvarado এবং অন্যদের (২০১৯) দ্বারা উত্থাপিত {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 এ সমরূপ হতে পারে তাদের শ্রেণী

প্রধান বৈশিষ্ট্য প্রমেয়

প্রস্তাব ৩: গ্রাফ শ্রেণী 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)।

প্রযুক্তিগত উদ্ভাবনী পয়েন্ট

১. আদিম ইতিবাচক নির্মাণ (Primitive Positive Constructions)

CSP এর মধ্যে হ্রাস সম্পর্ক স্থাপনের জন্য pp-নির্মাণ ব্যবহার করে, যা গ্রাফ তত্ত্বে gadget হ্রাসের সাথে সামঞ্জস্যপূর্ণ।

২. সর্বজনীন গ্রাফ তত্ত্ব

বংশগত গ্রাফ শ্রেণী C\mathcal{C} এর জন্য, যদি একটি সর্বজনীন গ্রাফ HH বিদ্যমান থাকে (অর্থাৎ Age(H)=C(H) = \mathcal{C}), তাহলে SP(C)=CSP(H∗)(\mathcal{C}) = \text{CSP}(H^*)।

३. বিভাজন প্রসারণ বন্ধতা

  • প্রসারণ: twins যোগ করা (একই প্রতিবেশী সহ শীর্ষবিন্দু)
  • সহ-প্রসারণ: co-twins যোগ করা (একে অপরের বাদে একই প্রতিবেশী)
  • বিভাজন প্রসারণ: শীর্ষবিন্দু বিভাজন (I,C)(I,C) অনুযায়ী প্রসারণ বা সহ-প্রসারণ

পরীক্ষামূলক সেটআপ

তাত্ত্বিক যাচাইকরণ

এই পেপারটি প্রধানত তাত্ত্বিক কাজ, নিম্নলিখিত উপায়ে পদ্ধতির কার্যকারিতা যাচাই করে:

  1. পরিচিত ফলাফল পুনরুৎপাদন: CSP পদ্ধতি ব্যবহার করে পরিচিত স্যান্ডউইচ সমস্যার জটিলতার ফলাফল পুনরায় প্রমাণ করে
  2. নতুন ফলাফল উদ্ভাবন: CSP তত্ত্বের সরঞ্জাম ব্যবহার করে নতুন জটিলতা শ্রেণীবিভাগ পায়
  3. গণনামূলক যাচাইকরণ: কিছু সীমিত কাঠামোর বহুরূপতা কম্পিউটার প্রোগ্রাম দ্বারা যাচাই করা হয়

বিশ্লেষণ সরঞ্জাম

  • Datalog প্রোগ্রাম: নির্দিষ্ট বহুপদ সময় সমাধানযোগ্য CSP সমাধান করে
  • MMSNP হ্রাস: অসীম ডোমেইন CSP কে সীমিত ডোমেইনে হ্রাস করে
  • বীজগণিত পদ্ধতি: বহুরূপতা ব্যবহার করে CSP জটিলতা বিশ্লেষণ করে

পরীক্ষামূলক ফলাফল

প্রধান জটিলতার ফলাফল

১. লাইন গ্রাফ সম্পর্কিত

  • প্রমেয়: বহুগ্রাফের লাইন গ্রাফের স্যান্ডউইচ সমস্যা NP-সম্পূর্ণ
  • প্রমেয়: দ্বিপক্ষীয় বহুগ্রাফের লাইন গ্রাফের স্যান্ডউইচ সমস্যা NP-সম্পূর্ণ

२. নিষিদ্ধ উপগ্রাফ শ্রেণী

  • অনুসিদ্ধান্ত ১৮: k≥4k \geq 4 এর জন্য, {P4,Kk}\{P_4,K_k\}-মুক্ত গ্রাফ, {P4,Ik}\{P_4,I_k\}-মুক্ত গ্রাফ এবং KkK_k-মুক্ত নিখুঁত গ্রাফের স্যান্ডউইচ সমস্যা সবই NP-সম্পূর্ণ
  • প্রমেয় ১७: FF যদি অ-সম্পূর্ণ বিন্দু নির্ধারক গ্রাফের সেট হয় এবং FF-মুক্ত গ্রাফ সবই নিখুঁত হয়, তাহলে k≥4k \geq 4 এর জন্য, (F∪{Kk})(F \cup \{K_k\})-মুক্ত গ্রাফের স্যান্ডউইচ সমস্যা NP-কঠিন

३. পথ নিষেধ

  • প্রমেয় २०: n,k≥4n,k \geq 4 এর জন্য, {Pn,Kk}\{P_n,K_k\}-মুক্ত গ্রাফের স্যান্ডউইচ সমস্যা NP-সম্পূর্ণ

অ্যালগরিদমিক জটিলতা শ্রেণীবিভাগ

বহুপদ সময় সমাধানযোগ্য ক্ষেত্র

  • বিভাজিত গ্রাফ: ২-SAT হ্রাসের মাধ্যমে
  • থ্রেশহোল্ড গ্রাফ: সম্পূর্ণ প্রতিসাম্য বহুরূপতা ব্যবহার করে
  • সম্পূর্ণ বহু-অংশ গ্রাফ: Datalog প্রোগ্রাম সমাধান

NP-সম্পূর্ণ ক্ষেত্র

  • তুলনা গ্রাফ: র্যান্ডম আংশিক অর্ডারের CSP হ্রাসের মাধ্যমে
  • ক্রমপরিবর্তন গ্রাফ: betweenness সমস্যা হ্রাসের মাধ্যমে
  • সাধারণীকৃত বিভাজিত গ্রাফ: (p,q)(p,q)-বিভাজিত গ্রাফ যখন p+q>2p+q > 2

অ-দ্বিপক্ষীয় ফলাফল

প্রমেয় २१: যদি P ≠\neq coNP হয়, তাহলে একটি গ্রাফ শ্রেণী C\mathcal{C} বিদ্যমান যাতে SP(C)(\mathcal{C}) coNP-মধ্যবর্তী হয়।

নির্মাণ Ladner প্রমেয়ের অভিযোজনের উপর ভিত্তি করে, প্রমাণ করে যে গ্রাফ স্যান্ডউইচ সমস্যার জটিলতা P বনাম NP দ্বিপক্ষীয়তার বাইরে যায়।

সম্পর্কিত কাজ

গ্রাফ স্যান্ডউইচ সমস্যা গবেষণা

  • Golumbic এবং অন্যরা (১৯९५): প্রথম পদ্ধতিগত গ্রাফ স্যান্ডউইচ সমস্যা গবেষণা
  • পরবর্তী কাজ: নির্দিষ্ট গ্রাফ শ্রেণীর জটিলতা শ্রেণীবিভাগ
  • উন্মুক্ত সমস্যা: নিখুঁত গ্রাফ স্যান্ডউইচ সমস্যার জটিলতা অনির্ধারিত

সীমাবদ্ধতা সন্তুষ্টি তত্ত্ব

  • Schaefer প্রমেয়: বুলিয়ান ডোমেইন CSP এর দ্বিপক্ষীয়তা
  • Hell-Nešetřil প্রমেয়: গ্রাফ সমরূপতা সমস্যা শ্রেণীবিভাগ
  • সীমিত ডোমেইন দ্বিপক্ষীয়তা: Bulatov এবং Zhuk এর যুগান্তকারী ফলাফল
  • অসীম ডোমেইন CSP: সময়ানুবর্তী CSP এর মতো বিশেষ ক্ষেত্রের শ্রেণীবিভাগ

প্রযুক্তিগত সংযোগ

এই পেপারটি প্রথমবারের মতো গ্রাফ স্যান্ডউইচ সমস্যা এবং অসীম ডোমেইন CSP এর মধ্যে পদ্ধতিগত সংযোগ স্থাপন করে, দুটি ক্ষেত্রের ক্রস-ডোমেইন সহযোগিতার জন্য নতুন দৃষ্টিভঙ্গি প্রদান করে।

উপসংহার এবং আলোচনা

প্রধান উপসংহার

  1. তাত্ত্বিক একীকরণ: গ্রাফ স্যান্ডউইচ সমস্যা পদ্ধতিগতভাবে CSP তত্ত্ব দিয়ে বিশ্লেষণ করা যায়
  2. পদ্ধতির কার্যকারিতা: CSP সরঞ্জাম জটিলতার প্রমাণ সরল করতে এবং নতুন ফলাফল আবিষ্কার করতে পারে
  3. জটিলতার সমৃদ্ধি: স্যান্ডউইচ সমস্যা P থেকে coNP-মধ্যবর্তী পর্যন্ত সম্পূর্ণ জটিলতা বর্ণালী প্রদর্শন করে

সীমাবদ্ধতা

  1. প্রযোজ্যতার পরিসীমা: শুধুমাত্র নির্দিষ্ট শর্ত পূরণকারী গ্রাফ শ্রেণীতে প্রযোজ্য (বংশগত, JEP, বিভাজন প্রসারণ বন্ধ)
  2. নিখুঁত গ্রাফ সমস্যা: সবচেয়ে গুরুত্বপূর্ণ উন্মুক্ত সমস্যা (নিখুঁত গ্রাফ স্যান্ডউইচ সমস্যা) এখনও সমাধান হয়নি
  3. গঠনমূলক: কিছু অস্তিত্ব ফলাফল কার্যকর নির্মাণ অ্যালগরিদমের অভাব রয়েছে

ভবিষ্যত দিকনির্দেশনা

  1. ω-শ্রেণীবদ্ধ কাঠামো: ω-শ্রেণীবদ্ধ গ্রাফ শ্রেণীর স্যান্ডউইচ সমস্যা গবেষণা করা
  2. নিখুঁত গ্রাফ সমস্যা: নিখুঁত গ্রাফ স্যান্ডউইচ সমস্যার সমাধান খোঁজা
  3. সিদ্ধান্তযোগ্যতা: নিষিদ্ধ উপগ্রাফের সেট দেওয়া হলে জটিলতার সিদ্ধান্তযোগ্যতা গবেষণা করা
  4. NP-মধ্যবর্তী: NP-মধ্যবর্তী গ্রাফ স্যান্ডউইচ সমস্যা খোঁজা

গভীর মূল্যায়ন

সুবিধা

  1. তাত্ত্বিক উদ্ভাবন: প্রথমবারের মতো গ্রাফ স্যান্ডউইচ সমস্যা এবং CSP তত্ত্বের মধ্যে পদ্ধতিগত সংযোগ স্থাপন করে, একটি একীভূত বিশ্লেষণ কাঠামো প্রদান করে
  2. পদ্ধতির কমনীয়তা: pp-নির্মাণ ইত্যাদি CSP সরঞ্জাম ব্যবহার করে জটিলতার প্রমাণ উল্লেখযোগ্যভাবে সরল করে
  3. সমৃদ্ধ ফলাফল: একাধিক উন্মুক্ত সমস্যা সমাধান করে, প্রচুর নতুন জটিলতার ফলাফল প্রদান করে
  4. প্রযুক্তিগত গভীরতা: গ্রাফ তত্ত্ব, মডেল তত্ত্ব, গণনামূলক জটিলতা ইত্যাদি একাধিক ক্ষেত্রের গভীর তত্ত্ব একত্রিত করে

অপূর্ণতা

  1. প্রযোজ্যতার সীমাবদ্ধতা: কাঠামো শুধুমাত্র নির্দিষ্ট ধরনের গ্রাফ শ্রেণীতে প্রযোজ্য, সম্পূর্ণ সর্বজনীন নয়
  2. ব্যবহারিকতা: প্রধানত তাত্ত্বিক অবদান, বাস্তব অ্যালগরিদম উন্নতি সীমিত
  3. নিখুঁত গ্রাফ: মূল উন্মুক্ত সমস্যা এখনও সমাধান হয়নি

প্রভাব

  1. একাডেমিক মূল্য: গ্রাফ স্যান্ডউইচ সমস্যা গবেষণার জন্য নতুন তাত্ত্বিক সরঞ্জাম এবং দৃষ্টিভঙ্গি প্রদান করে
  2. ক্রস-ডোমেইন তাৎপর্য: গ্রাফ তত্ত্ব এবং CSP তত্ত্বের ক্রস-ডোমেইন সংমিশ্রণ প্রচার করে
  3. পদ্ধতিগত অবদান: pp-নির্মাণের গ্রাফ তত্ত্বের জটিলতা বিশ্লেষণে প্রয়োগ প্রদর্শনীয় মূল্য রাখে

প্রযোজ্য পরিস্থিতি

এই পদ্ধতি বিশেষভাবে উপযুক্ত:

  1. ভাল কাঠামোগত সম্পত্তি সহ বংশগত গ্রাফ শ্রেণী
  2. সর্বজনীন গ্রাফ বিদ্যমান গ্রাফ শ্রেণী
  3. পদ্ধতিগত জটিলতা বিশ্লেষণের প্রয়োজন এমন গ্রাফ তত্ত্ব সমস্যা

সংদর্ভ

পেপারটি ৬১টি সম্পর্কিত সাহিত্য উদ্ধৃত করে, প্রধানত অন্তর্ভুক্ত:

  • গ্রাফ স্যান্ডউইচ সমস্যার ভিত্তিস্থাপনকারী কাজ ৩८
  • CSP তত্ত্বের মূল ফলাফল २०,५९,६०
  • অসীম ডোমেইন CSP এর শ্রেণীবিভাগ ফলাফল १०,११,४६
  • গ্রাফ তত্ত্বে কাঠামোগত ফলাফল २२,२३,३७,४७

সারাংশ: এই পেপারটি গ্রাফ স্যান্ডউইচ সমস্যা এবং সীমাবদ্ধতা সন্তুষ্টি সমস্যার মধ্যে গভীর সংযোগ স্থাপনের মাধ্যমে, এই ক্লাসিক গ্রাফ তত্ত্ব সমস্যার জন্য একটি সম্পূর্ণ নতুন তাত্ত্বিক বিশ্লেষণ কাঠামো প্রদান করে। যদিও সমস্ত স্যান্ডউইচ সমস্যা সম্পূর্ণভাবে সমাধানে এখনও সীমাবদ্ধতা রয়েছে, তবে এর তাত্ত্বিক অবদান এবং পদ্ধতিগত উদ্ভাবন সম্পর্কিত গবেষণার জন্য নতুন পথ উন্মোচন করে।