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
  • শিরোনাম: দ্বিপক্ষীয় গ্রাফকে ছোট চক্রে সংকুচিত করার জটিলতা
  • লেখক: R. Krithika, Roohani Sharma, Prafullkumar Tale
  • শ্রেণীবিভাগ: cs.CC (গণনামূলক জটিলতা তত্ত্ব)
  • প্রকাশনার সময়/সম্মেলন: গ্রাফ-তাত্ত্বিক ধারণা সম্পর্কিত কম্পিউটার বিজ্ঞানে ৪৮তম আন্তর্জাতিক কর্মশালা (WG2022)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2206.07358

সারসংক্ষেপ

ধনাত্মক পূর্ণসংখ্যা ℓ≥3\ell \geq 3 এর জন্য, CℓC_\ell-সংকোচনযোগ্যতা সমস্যা একটি অনির্দেশিত সরল গ্রাফ GG ইনপুট হিসাবে নেয় এবং নির্ধারণ করে যে GG কে প্রান্ত সংকোচন অপারেশনের মাধ্যমে CℓC_\ell (ℓ\ell টি শীর্ষবিন্দু সহ প্ররোচিত চক্র) এর সাথে সমরূপ একটি গ্রাফে রূপান্তরিত করা যায় কিনা। Brouwer এবং Veldman ১৯৮৭ সালে প্রমাণ করেছেন যে C4C_4-সংকোচনযোগ্যতা সাধারণ গ্রাফে NP-সম্পূর্ণ। C3C_3-সংকোচনযোগ্যতা বহুপদী সময়ে সমাধানযোগ্য। Dabrowski এবং Paulusma ২০১৭ সালে প্রমাণ করেছেন যে ℓ=6\ell = 6 হলে, CℓC_\ell-সংকোচনযোগ্যতা দ্বিপক্ষীয় গ্রাফে NP-সম্পূর্ণ এবং ℓ=4\ell = 4 বা 55 হলে সমস্যার জটিলতা সম্পর্কে একটি উন্মুক্ত প্রশ্ন উত্থাপন করেছেন। এই পেপারটি প্রমাণ করে যে C5C_5-সংকোচনযোগ্যতা এবং C4C_4-সংকোচনযোগ্যতা উভয়ই দ্বিপক্ষীয় গ্রাফে NP-সম্পূর্ণ।

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

সমস্যার পটভূমি

  1. গ্রাফ সংকোচন অপারেশন: প্রান্ত সংকোচন গ্রাফ তত্ত্বে একটি মৌলিক অপারেশন, যা একটি প্রান্তের দুটি প্রান্তবিন্দু মুছে ফেলে এবং নতুন শীর্ষবিন্দুকে মূল প্রান্তবিন্দুর সমস্ত প্রতিবেশীর সাথে সংযুক্ত করে গ্রাফকে সরল করে। এই অপারেশনের ক্লাস্টারিং, সংকোচন, বিরলকরণ এবং কম্পিউটার গ্রাফিক্সে গুরুত্বপূর্ণ প্রয়োগ রয়েছে।
  2. চক্র সংকোচন সমস্যা: CℓC_\ell-সংকোচনযোগ্যতা সমস্যা নির্ধারণ করে যে প্রদত্ত গ্রাফ প্রান্ত সংকোচন অপারেশনের মাধ্যমে ℓ\ell-চক্রে রূপান্তরিত হতে পারে কিনা। এই সমস্যা গ্রাফের "চক্রশীলতা" (cyclicity) পরামিতির সাথে ঘনিষ্ঠভাবে সম্পর্কিত, যা গ্রাফ সংকুচিত হতে পারে এমন সর্বাধিক চক্রের দৈর্ঘ্য হিসাবে সংজ্ঞায়িত।
  3. জটিলতা গবেষণার বর্তমান অবস্থা:
    • C3C_3-সংকোচনযোগ্যতা: বহুপদী সময়ে সমাধানযোগ্য
    • C4C_4-সংকোচনযোগ্যতা: সাধারণ গ্রাফে NP-সম্পূর্ণ
    • CℓC_\ell-সংকোচনযোগ্যতা (ℓ≥5\ell \geq 5): সাধারণ গ্রাফে NP-সম্পূর্ণ
    • C6C_6-সংকোচনযোগ্যতা: দ্বিপক্ষীয় গ্রাফে NP-সম্পূর্ণ

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

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

মূল অবদান

  1. প্রধান তাত্ত্বিক ফলাফল: প্রমাণ করা হয়েছে যে C5C_5-সংকোচনযোগ্যতা এবং C4C_4-সংকোচনযোগ্যতা উভয়ই দ্বিপক্ষীয় গ্রাফে NP-সম্পূর্ণ
  2. গঠনমূলক প্রমাণ: Positive NAE-SAT সমস্যা থেকে বহুপদী সময় হ্রাসের মাধ্যমে গঠনমূলক প্রমাণ প্রদান করা হয়েছে
  3. প্রযুক্তিগত উদ্ভাবন:
    • C5C_5 সমস্যার জন্য, দ্বি-পদক্ষেপ নির্মাণ পদ্ধতি ডিজাইন করা হয়েছে: প্রথমে অ-দ্বিপক্ষীয় গ্রাফ HH তৈরি করা, তারপর প্রান্ত বিভাজনের মাধ্যমে দ্বিপক্ষীয় গ্রাফ GG পাওয়া
    • C4C_4 সমস্যার জন্য, সরাসরি দ্বিপক্ষীয় গ্রাফ তৈরি এবং এর সমতুল্যতা প্রমাণ করা হয়েছে
  4. সম্প্রসারিত ফলাফল: প্রমাণ করা হয়েছে যে C4C_4-সংকোচনযোগ্যতা ব্যাস ২ এর K4K_4-মুক্ত গ্রাফে NP-সম্পূর্ণ

পদ্ধতির বিস্তারিত বিবরণ

কাজের সংজ্ঞা

ইনপুট: দ্বিপক্ষীয় গ্রাফ G=(V,E)G = (V, E)আউটপুট: নির্ধারণ করুন যে GG কে প্রান্ত সংকোচন অপারেশনের মাধ্যমে CℓC_\ell (ℓ∈{4,5}\ell \in \{4,5\}) এ রূপান্তরিত করা সম্ভব কিনা সীমাবদ্ধতা: শুধুমাত্র প্রান্ত সংকোচন অপারেশন ব্যবহার করা যায়, শীর্ষবিন্দু মুছে ফেলা বা প্রান্ত যোগ করা যায় না

প্রমাণ কৌশল

C5C_5-সংকোচনযোগ্যতার প্রমাণ

প্রথম পদক্ষেপ: অ-দ্বিপক্ষীয় গ্রাফ HH তৈরি করা Positive NAE-SAT উদাহরণ ψ\psi (NN টি চলক, MM টি ধারা) দেওয়া:

  1. মৌলিক চক্র: ৫টি শীর্ষবিন্দু Vα={α0,α1,α2,α3,α4}V_\alpha = \{\alpha_0, \alpha_1, \alpha_2, \alpha_3, \alpha_4\} যোগ করে ৫-চক্র তৈরি করা
  2. চলক যন্ত্র: প্রতিটি চলক XiX_i এর জন্য, ৫-চক্র 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 তৈরি করাHH এর নির্দিষ্ট প্রান্ত সেটের বিভাজনের মাধ্যমে দ্বিপক্ষীয় গ্রাফ GG তৈরি করা:

  • প্রান্ত α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-সংকোচনযোগ্যতার প্রমাণ

সরাসরি দ্বিপক্ষীয় গ্রাফ 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. সাক্ষ্য কাঠামো বিশ্লেষণ: "সুন্দর সাক্ষ্য কাঠামো" ধারণা প্রবর্তন করা, C4C_4-সাক্ষ্য কাঠামোর বৈশিষ্ট্য পদ্ধতিগতভাবে বিশ্লেষণ করা
  3. হ্রাসের সঠিকতা প্রমাণ:
    • নির্মিত গ্রাফের দ্বিপক্ষীয়তা প্রমাণ করা
    • মূল সমস্যা এবং নির্মিত গ্রাফের সমতুল্যতা প্রমাণ করা
    • SAT সমস্যার সমাধানের সাথে দ্বিমুখী সম্পর্ক স্থাপন করা

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

এই পেপারটি বিশুদ্ধ তাত্ত্বিক গবেষণা, যা পরীক্ষামূলক যাচাইকরণ জড়িত নয়। সমস্ত ফলাফল গাণিতিক প্রমাণের মাধ্যমে প্রাপ্ত।

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

প্রধান তাত্ত্বিক ফলাফল

উপপাদ্য ১: C5C_5-সংকোচনযোগ্যতা দ্বিপক্ষীয় গ্রাফে NP-সম্পূর্ণ উপপাদ্য ২: C4C_4-সংকোচনযোগ্যতা দ্বিপক্ষীয় গ্রাফে NP-সম্পূর্ণ উপপাদ্য ৩: C4C_4-সংকোচনযোগ্যতা ব্যাস ২ এর K4K_4-মুক্ত গ্রাফে NP-সম্পূর্ণ

প্রমাণের মূল বিষয়

  1. NP অন্তর্ভুক্তি: প্রদত্ত সাক্ষ্য কাঠামো বহুপদী সময়ে যাচাই করা যায়
  2. NP-কঠোরতা: পরিচিত NP-সম্পূর্ণ সমস্যা Positive NAE-SAT থেকে বহুপদী সময় হ্রাসের মাধ্যমে
  3. নির্মাণ জটিলতা: সমস্ত নির্মাণ বহুপদী সময়ে সম্পন্ন হয়

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

ঐতিহাসিক উন্নয়ন

  1. Brouwer & Veldman (1987): সাধারণ গ্রাফে C4C_4-সংকোচনযোগ্যতার NP-সম্পূর্ণতা প্রমাণ করা
  2. Hammack (1999, 2002): সমতল গ্রাফে চক্র সংকোচন সমস্যা অধ্যয়ন করা
  3. Dabrowski & Paulusma (2017): দ্বিপক্ষীয় গ্রাফে C6C_6-সংকোচনযোগ্যতার NP-সম্পূর্ণতা প্রমাণ করা

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

  1. পথ সংকোচন সমস্যা: PℓP_\ell-সংকোচনযোগ্যতা কিছু গ্রাফ শ্রেণীতে বহুপদী সময়ে সমাধানযোগ্য
  2. সাধারণ HH-সংকোচন সমস্যা: বিভিন্ন গ্রাফ শ্রেণীতে জটিলতা বিশ্লেষণ
  3. প্যারামিটারাইজড জটিলতা: প্যারামিটারাইজড দৃষ্টিকোণ থেকে সংকোচন সমস্যা অধ্যয়ন করা

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

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

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

সীমাবদ্ধতা

  1. নির্মাণ জটিলতা: হ্রাস নির্মাণের গ্রাফ স্কেল বৃহৎ, বাস্তব প্রয়োগে দক্ষতা কম হতে পারে
  2. প্যারামিটারাইজড বিশ্লেষণ: সমস্যা প্যারামিটারাইজড জটিলতার দৃষ্টিকোণ থেকে বিশ্লেষণ করা হয়নি
  3. আনুমানিক অ্যালগরিদম: আনুমানিক অ্যালগরিদমের সম্ভাবনা আলোচনা করা হয়নি

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

  1. অন্যান্য গ্রাফ শ্রেণী: অন্যান্য সীমাবদ্ধ গ্রাফ শ্রেণীতে জটিলতা অধ্যয়ন করা
  2. প্যারামিটারাইজড অ্যালগরিদম: স্থির প্যারামিটার ট্র্যাক্টেবল অ্যালগরিদম উন্নয়ন করা
  3. আনুমানিক অ্যালগরিদম: গ্যারান্টিযুক্ত আনুমানিক অনুপাত সহ অ্যালগরিদম ডিজাইন করা
  4. দীর্ঘতম চক্র সমস্যা: গ্রাফের চক্রশীলতা পরামিতি গণনার জটিলতা অধ্যয়ন করা

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

শক্তি

  1. তাত্ত্বিক সম্পূর্ণতা: গুরুত্বপূর্ণ উন্মুক্ত সমস্যা সম্পূর্ণভাবে সমাধান করা, অত্যন্ত উচ্চ তাত্ত্বিক মূল্য রয়েছে
  2. প্রযুক্তিগত উদ্ভাবন: দ্বি-পদক্ষেপ নির্মাণ পদ্ধতি এবং সুন্দর সাক্ষ্য কাঠামো ধারণা পদ্ধতিগত অর্থ রয়েছে
  3. প্রমাণ কঠোরতা: সমস্ত উপপাদ্যের সম্পূর্ণ গাণিতিক প্রমাণ রয়েছে, যুক্তি স্পষ্ট
  4. লেখার গুণমান: পেপার কাঠামো যুক্তিসঙ্গত, অভিব্যক্তি স্পষ্ট, চিত্র সহায়ক ব্যাখ্যা কার্যকর

অপূর্ণতা

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

প্রভাব

  1. একাডেমিক অবদান: গণনামূলক জটিলতা তত্ত্বের গুরুত্বপূর্ণ শূন্যস্থান পূরণ করা
  2. পদ্ধতিগত মূল্য: প্রদত্ত প্রযুক্তিগত পদ্ধতি অনুরূপ সমস্যা গবেষণায় ব্যবহার করা যায়
  3. পরবর্তী গবেষণা: সম্পর্কিত ক্ষেত্রের আরও গবেষণার জন্য ভিত্তি স্থাপন করা

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

  1. তাত্ত্বিক গবেষণা: গ্রাফ তত্ত্ব এবং গণনামূলক জটিলতা তত্ত্ব গবেষণা
  2. অ্যালগরিদম ডিজাইন: সম্পর্কিত অ্যালগরিদম ডিজাইনের জন্য জটিলতা তত্ত্ব নির্দেশনা প্রদান করা
  3. শিক্ষা প্রয়োগ: NP-সম্পূর্ণতা প্রমাণের ক্লাসিক কেস হিসাবে

তথ্যসূত্র

পেপারটি ২৯টি সম্পর্কিত তথ্যসূত্র উদ্ধৃত করে, যা অন্তর্ভুক্ত করে:

  • গ্রাফ সংকোচন সমস্যার প্রাথমিক কাজ
  • গণনামূলক জটিলতা তত্ত্বের ভিত্তি
  • সম্পর্কিত NP-সম্পূর্ণতা ফলাফল
  • গ্রাফ তত্ত্বের মৌলিক তত্ত্ব

প্রধান তথ্যসূত্রগুলির মধ্যে রয়েছে Brouwer & Veldman (1987), Dabrowski & Paulusma (2017), Garey & Johnson (1979) এবং অন্যান্য ক্লাসিক কাজ।