প্রান্তিক মুছে ফেলার মাধ্যমে গ্রাফ অনিয়মিততা

মৌলিক তথ্য

• কাগজ আইডি: 2511.14514
• শিরোনাম: Graph Irregularity via Edge Deletions
• লেখক: Julien Bensmail, Noémie Catherinot, Foivos Fioravantes, Clara Marcille, Nacim Oijid
• শ্রেণীবিভাগ: math.CO (সমন্বয়মূলক গণিত), cs.CC (গণনামূলক জটিলতা), cs.DM (বিচ্ছিন্ন গণিত)
• প্রকাশনার সময়: ২০২৫ সালের ১৮ নভেম্বর (arXiv প্রাক-প্রিন্ট)
• কাগজের লিঙ্ক: https://arxiv.org/abs/2511.14514

সারসংক্ষেপ

এই কাগজটি গ্রাফের প্রান্তিক অনিয়মিততা সমস্যা অধ্যয়ন করে, যা Ie(G) প্যারামিটার দ্বারা প্রতিনিধিত্ব করা হয়, যা গ্রাফ G কে স্থানীয়ভাবে অনিয়মিত গ্রাফে রূপান্তরিত করার জন্য সর্বনিম্ন k প্রান্তিক মুছে ফেলার সংখ্যা নির্দেশ করে (যেখানে যেকোনো দুটি সংলগ্ন শীর্ষবিন্দুর ডিগ্রি ভিন্ন)। যদিও এই সমস্যাটি NP-কঠিন এবং W1-কঠিন হিসাবে প্রমাণিত হয়েছে, লেখকরা দুটি FPT অ্যালগরিদম প্রস্তাব করেছেন: একটি সমাধানের আকার এবং সর্বোচ্চ ডিগ্রি ∆ সম্পর্কে, এবং অন্যটি শীর্ষবিন্দু কভার সংখ্যা সম্পর্কে। উপরন্তু, লেখকরা ঘন গ্রাফ, বিশেষত সম্পূর্ণ গ্রাফ সম্পর্কে গভীর গবেষণা করেছেন এবং একটি গুরুত্বপূর্ণ অনুমান প্রস্তাব করেছেন: যেকোনো সংযুক্ত গ্রাফ G এর জন্য, Ie(G) ≤ m/3 + c, যেখানে m হল প্রান্তিক সংখ্যা এবং c একটি ধ্রুবক। এই অনুমানটি একাধিক গ্রাফ শ্রেণীতে (গাছ সহ) যাচাই করা হয়েছে।

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

সমস্যার সংজ্ঞা

গ্রাফ তত্ত্বে, নিয়মিত গ্রাফ সেই গ্রাফকে প্রতিনিধিত্ব করে যেখানে সমস্ত শীর্ষবিন্দুর ডিগ্রি একই। দ্বৈত ধারণা হিসাবে, গবেষকরা অনিয়মিততার একাধিক সংজ্ঞা প্রস্তাব করেছেন:

1. অনিয়মিত গ্রাফ: সমস্ত শীর্ষবিন্দুর ডিগ্রি পরস্পর ভিন্ন
2. অত্যন্ত অনিয়মিত গ্রাফ: প্রতিটি শীর্ষবিন্দুর প্রতিবেশী ডিগ্রি সবই ভিন্ন
3. স্থানীয়ভাবে অনিয়মিত গ্রাফ: যেকোনো দুটি সংলগ্ন শীর্ষবিন্দুর ডিগ্রি ভিন্ন

এই কাগজটি স্থানীয়ভাবে অনিয়মিত গ্রাফ এই ধারণায় মনোনিবেশ করে।

গবেষণার গুরুত্ব

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

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

• Fioravantes এবং অন্যরা 10 সম্প্রতি প্রান্তিক অনিয়মিততা সাবগ্রাফের ধারণা প্রবর্তন করেছেন এবং সর্বোত্তম প্রান্তিক অনিয়মিততা সাবগ্রাফ গণনা করা NP-কঠিন তা প্রমাণ করেছেন
• এই সমস্যাটি সমাধানের আকার এবং প্রতিক্রিয়া শীর্ষবিন্দু সেট সম্পর্কে W1-কঠিন
• ঘন গ্রাফ (যেমন সম্পূর্ণ গ্রাফ) এবং নির্দিষ্ট কাঠামোগত প্যারামিটার (প্রতিবেশী বৈচিত্র্য, ক্লিকের দূরত্ব) সম্পর্কে আচরণ এখনও অস্পষ্ট

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

লেখকরা লক্ষ্য রাখেন:

1. নির্দিষ্ট প্যারামিটারের জন্য দক্ষ FPT অ্যালগরিদম ডিজাইন করতে
2. বিভিন্ন গ্রাফ শ্রেণীর Ie(G) এর সঠিক মান বা উপরের সীমা বুঝতে
3. Ie(G) এবং গ্রাফের প্রান্তিক সংখ্যা m এর মধ্যে সর্বজনীন সম্পর্ক অন্বেষণ করতে

মূল অবদান

1. প্যারামিটারযুক্ত অ্যালগরিদম:
   • সমাধান আকার k এবং সর্বোচ্চ ডিগ্রি ∆ সম্পর্কে FPT অ্যালগরিদম প্রস্তাব করুন, কার্নেল আকার O(k∆^(2k+2))
   • শীর্ষবিন্দু কভার সংখ্যা vc সম্পর্কে FPT অ্যালগরিদম প্রস্তাব করুন, সময় জটিলতা 2^O(vc^4)·n^O(1), পূর্ববর্তী ILP-ভিত্তিক পদ্ধতির চেয়ে উন্নত
2. কাঠামোগত ফলাফল:
   • পথ এবং চক্রের জন্য, Ie এর সঠিক সূত্র প্রমাণ করুন
   • সম্পূর্ণ দ্বিপক্ষীয় গ্রাফ Kn,m এর জন্য প্রমাণ করুন: Ie = 0 যখন n≠m, Ie = n যখন n=m
   • গাছ T এর জন্য প্রমাণ করুন: Ie(T) ≤ |E(T)|/3 (যদি না T একটি পথ হয়)
   • ত্রিভুজ সংখ্যা tk এর ক্রম সহ সম্পূর্ণ গ্রাফের জন্য, সঠিক সূত্র প্রদান করুন: Ie(Ktk) = |E(Ktk)| - k(k+1)(k-1)(3k+2)/24
3. গুরুত্বপূর্ণ অনুমান (অনুমান 1): একটি ধ্রুবক c বিদ্যমান যাতে যেকোনো সংযুক্ত গ্রাফ G এর জন্য m প্রান্তিক সহ, Ie(G) ≤ m/3 + c
4. তাত্ত্বিক অন্তর্দৃষ্টি:
   • Ie(G) এর একটি সাধারণ নিম্ন সীমা প্রদান করুন: Ie(G) ≥ ⌈conf(G)/(2∆-1)⌉
   • প্রমাণ করুন যে সর্বোত্তম প্রান্তিক অনিয়মিততা সাবগ্রাফে প্রান্তিকগুলি দ্বন্দ্ব প্রান্তিকের কাছাকাছি থাকতে হবে (লেমা 1)

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

কাজের সংজ্ঞা

ইনপুট: গ্রাফ G = (V, E) এবং ইতিবাচক পূর্ণসংখ্যা k ≥ 1
আউটপুট: নির্ধারণ করুন Ie(G) ≤ k কিনা (সিদ্ধান্ত সংস্করণ) বা সর্বোত্তম প্রান্তিক অনিয়মিততা সাবগ্রাফ গণনা করুন (অপ্টিমাইজেশন সংস্করণ)

সংজ্ঞা:

• গ্রাফ G স্থানীয়ভাবে অনিয়মিত, যদি যেকোনো প্রান্তিক uv ∈ E এর জন্য, dG(u) ≠ dG(v)
• প্রান্তিক অনিয়মিততা সাবগ্রাফ: প্রান্তিক সেট S ⊆ E যাতে G-S স্থানীয়ভাবে অনিয়মিত
• Ie(G): সর্বনিম্ন প্রান্তিক অনিয়মিততা সাবগ্রাফের আকার
• conf(G): দ্বন্দ্ব সংখ্যা, অর্থাৎ dG(u) = dG(v) সন্তুষ্ট করে এমন প্রান্তিক uv এর সংখ্যা

মূল প্রযুক্তিগত পদ্ধতি

1. k+∆ সম্পর্কে কার্নেলাইজেশন অ্যালগরিদম (উপপাদ্য 2)

মূল লেমা 1: S যদি G এর সর্বোত্তম প্রান্তিক অনিয়মিততা সাবগ্রাফ হয়, তাহলে S এর যেকোনো প্রান্তিক e থেকে কোনো দ্বন্দ্ব প্রান্তিকের দূরত্ব সর্বাধিক 2|S|-1।

প্রমাণের চিন্তাধারা (আবেগপ্রবণ পদ্ধতি):

• ভিত্তি: k=1 এর সময়, একমাত্র মুছে ফেলা প্রান্তিক অবশ্যই কোনো দ্বন্দ্বের সাথে সংলগ্ন হতে হবে
• আবেগপ্রবণ: k≥2 এর জন্য, যেকোনো দ্বন্দ্ব uv এর জন্য, অবশ্যই e∈S বিদ্যমান যা u বা v এর সাথে সংলগ্ন; G-{e} এ আবেগপ্রবণ অনুমান প্রয়োগ করুন

কার্নেলাইজেশন নিয়ম:

1. যদি conf(G) ≥ k(2∆+1), না উদাহরণ ফেরত দিন
2. প্রতিটি দ্বন্দ্ব প্রান্তিক e এর জন্য, বল B(e, 2k+1) সংজ্ঞায়িত করুন যা e এর শেষ বিন্দু থেকে সর্বাধিক 2k+1 দূরত্বের সমস্ত শীর্ষবিন্দু ধারণ করে
3. সাবগ্রাফ H = G∪e∈EC Ve তৈরি করুন, যেখানে Ve হল e এর বল
4. H এ শীর্ষবিন্দু ডিগ্রি সামঞ্জস্য করুন যাতে এটি G এ একই হয় (পাতা যোগ করার মাধ্যমে)

কার্নেল আকার বিশ্লেষণ:

• দ্বন্দ্ব সংখ্যা |EC| ≤ k(2∆+1)
• প্রতিটি বল সর্বাধিক 2∆^(2k) শীর্ষবিন্দু ধারণ করে
• মোট শীর্ষবিন্দু সংখ্যা: |V(H)| ≤ 2k(2∆+1)∆^(2k+1) = O(k∆^(2k+2))

2. শীর্ষবিন্দু কভার সংখ্যা সম্পর্কে অ্যালগরিদম (উপপাদ্য 5)

অ্যালগরিদম কাঠামো:

1. C = {u1,...,uvc} সর্বনিম্ন শীর্ষবিন্দু কভার হোক, I = V\C স্বাধীন সেট হোক
2. I কে I1 এবং I2 তে বিভক্ত করুন:
   • I1: C এ কোনো ডিগ্রি ≤5vc শীর্ষবিন্দুর সাথে সংলগ্ন স্বাধীন সেট শীর্ষবিন্দু
   • I2: অন্যান্য স্বাধীন সেট শীর্ষবিন্দু
3. G1 = GC∪I1, G2 = GC∪I2 সংজ্ঞায়িত করুন
4. S1 = S∩E(G1) এর সমস্ত সম্ভাবনা গণনা করুন (সর্বাধিক 2^O(vc^4) ধরনের)
5. প্রতিটি S1 এর জন্য, সর্বনিম্ন S2⊆E2 গণনা করুন যাতে G-(S1∪S2) স্থানীয়ভাবে অনিয়মিত হয়

মূল পর্যবেক্ষণ (দাবি 7): S1 এর সাথে সামঞ্জস্যপূর্ণ যেকোনো সর্বোত্তম প্রান্তিক অনিয়মিততা সাবগ্রাফ S এর জন্য, |S∩E2| ≤ vc^2

অপ্টিমাইজেশন কৌশল (দাবি 8): u∈C এবং v1,v2∈I2 এর জন্য, যদি uv1∈S কিন্তু uv2∉S, তাহলে সমান সর্বোত্তম সমাধান পেতে বিনিময় করা যায়। তাই প্রতিটি u∈C এর জন্য শুধুমাত্র মুছে ফেলা প্রান্তিক সংখ্যা ki অনুমান করতে হবে, Σki ≤ vc^2 সন্তুষ্ট করে।

সময় জটিলতা: 2^(vc+5vc^2)^2 · vc^(vc^2) · n^2 = 2^O(vc^4) · n^O(1)

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

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

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

এই কাগজটি তাত্ত্বিক গবেষণা, প্রধানত গাণিতিক প্রমাণের মাধ্যমে ফলাফল যাচাই করে পরীক্ষার মাধ্যমে নয়। তবে একাধিক গ্রাফ শ্রেণীতে গঠনমূলক বিশ্লেষণ পরিচালিত হয়েছে:

অধ্যয়ন করা গ্রাফ শ্রেণী

1. পথ Pn এবং চক্র Cn
2. সম্পূর্ণ দ্বিপক্ষীয় গ্রাফ Kn,m
3. গাছ
4. সম্পূর্ণ গ্রাফ Kn (বিশেষত ত্রিভুজ সংখ্যার ক্রম)
5. সাধারণ সংযুক্ত দ্বিপক্ষীয় গ্রাফ
6. সাধারণ সংযুক্ত গ্রাফ

বিশ্লেষণ পদ্ধতি

• সঠিক সূত্র উদ্ভাবন: পথ, চক্র, নির্দিষ্ট সম্পূর্ণ গ্রাফের জন্য
• উপরের সীমা প্রমাণ: গাছ, দ্বিপক্ষীয় গ্রাফ, সাধারণ গ্রাফের জন্য
• গঠনমূলক প্রমাণ: সীমা অর্জনকারী নির্দিষ্ট প্রান্তিক অনিয়মিততা সাবগ্রাফ প্রদর্শন করুন
• পুনরাবৃত্তিমূলক অ্যালগরিদম: গাছের জন্য O(n∆^3) সঠিক গণনা অ্যালগরিদম

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

প্রধান ফলাফল

1. পথ এবং চক্র (উপপাদ্য 9)

n≥2 এর পথ Pn এর জন্য:

• Ie(Pn) = (n-1)/3, যখন n≡1 (mod 3)
• Ie(Pn) = ⌈(n-1)/3⌉, যখন n≡2 (mod 3)
• Ie(Pn) = ⌊(n-1)/3⌋, অন্যথায়

n≥3 এর চক্রের জন্য: Ie(Cn) = Ie(Pn) + 1

প্রমাণ কৌশল: পথকে ক্রমাগত তিন-প্রান্তিক গ্রুপে বিভক্ত করুন, প্রতিটি গ্রুপ থেকে কমপক্ষে একটি প্রান্তিক মুছে ফেলুন

2. সম্পূর্ণ দ্বিপক্ষীয় গ্রাফ (উপপাদ্য 10)

• Ie(Kn,m) = 0, যখন n≠m (ইতিমধ্যে স্থানীয়ভাবে অনিয়মিত)
• Ie(Kn,n) = n (একটি শীর্ষবিন্দুর সমস্ত প্রান্তিক মুছে ফেলুন)

3. গাছ (উপপাদ্য 13)

প্রধান উপপাদ্য: যেকোনো গাছ T এর জন্য, হয় T একটি পথ, অথবা Ie(T) ≤ |E(T)|/3

প্রমাণের চিন্তাধারা:

• তারকা এবং দ্বিতারকার সূক্ষ্ম বিভাজনের জন্য, কেন্দ্র থেকে দূরত্ব 2 এর প্রান্তিক মুছে ফেলুন
• সাধারণ গাছের জন্য, আবেগপ্রবণ পদ্ধতি ব্যবহার করুন, সবচেয়ে গভীর ডিগ্রি ≥3 শীর্ষবিন্দু নির্বাচন করুন
• বিস্তারিত কেস বিশ্লেষণ (সাবট্রি কাঠামো এবং ডিগ্রি অনুযায়ী)

অ্যালগরিদম ফলাফল (উপপাদ্য 15): গাছের Ie(G) সঠিকভাবে O(n∆^3) সময়ে গণনা করা যায়

4. সম্পূর্ণ গ্রাফ (উপপাদ্য 16)

ক্রম n = tk = k(k+1)/2 (k-তম ত্রিভুজ সংখ্যা) এর জন্য:

Ie(Ktk) = |E(Ktk)| - mk

যেখানে mk = k(k+1)(k-1)(3k+2)/24

নির্মাণ: সর্বোচ্চ প্রান্তিক সংখ্যার স্থানীয়ভাবে অনিয়মিত গ্রাফ Tk এর ডিগ্রি ক্রম রয়েছে: 1টি ডিগ্রি n-1 শীর্ষবিন্দু, 2টি ডিগ্রি n-2 শীর্ষবিন্দু, ..., k টি ডিগ্রি n-k শীর্ষবিন্দু

5. সাধারণ গ্রাফের উপরের সীমা

দ্বিপক্ষীয় গ্রাফ (উপপাদ্য 11): সর্বনিম্ন ডিগ্রি 1 এর সংযুক্ত দ্বিপক্ষীয় গ্রাফের জন্য: Ie(G) ≤ n-1

সাধারণ গ্রাফ (উপপাদ্য 12): যেকোনো সংযুক্ত গ্রাফের জন্য: Ie(G) ≤ ⌊m/2⌋ + n + ∆ - 2

অনুমান যাচাইকরণ

অনুমান 1: একটি ধ্রুবক c বিদ্যমান যাতে যেকোনো m প্রান্তিক সহ সংযুক্ত গ্রাফ G এর জন্য, Ie(G) ≤ m/3 + c

যাচাইকৃত গ্রাফ শ্রেণী:

• ✓ চক্র (c≥2)
• ✓ গাছ
• ✓ ত্রিভুজ সংখ্যার ক্রম সহ সম্পূর্ণ গ্রাফ
• ✓ সম্পূর্ণ দ্বিপক্ষীয় গ্রাফ
• ✓ উপপাদ্য 12 এর মাধ্যমে, সাধারণ গ্রাফ আরও দুর্বল সীমা সন্তুষ্ট করে

কঠোরতা (উপপাদ্য 1): গ্রাফ H এর প্রতিটি প্রান্তিক দুইবার সূক্ষ্ম বিভাজন করে পাওয়া গ্রাফ G এর জন্য: Ie(G) ≥ m/3 তাই 1/3 সহগ কঠোর।

মূল অন্তর্দৃষ্টি

1. দ্বন্দ্ব সমাধান দক্ষতা: একটি প্রান্তিক মুছে ফেলা সর্বাধিক 2∆-1 দ্বন্দ্ব সমাধান করে (মন্তব্য 1)
2. সংযোগ প্রয়োজনীয়তা: অনুমান 1 এ সংযোগ প্রয়োজনীয় (নিখুঁত ম্যাচিং সমস্ত প্রান্তিক মুছে ফেলা প্রয়োজন)
3. বিরল বনাম ঘন: বিরল গ্রাফ (যেমন গাছ) m/3 সীমা অর্জন করা সহজ, ঘন গ্রাফ (যেমন সম্পূর্ণ গ্রাফ) জটিল আচরণ প্রদর্শন করে

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

গ্রাফ অনিয়মিততা গবেষণার বর্ণালী

1. অনিয়মিত গ্রাফ 6: Chartrand এবং অন্যরা অনিয়মিত শক্তি প্রবর্তন করেছেন (irregularity strength), প্রান্তিকের বহুত্ব বৃদ্ধির মাধ্যমে সমস্ত ডিগ্রি ভিন্ন করতে
2. অত্যন্ত অনিয়মিত গ্রাফ 1,5: Alavi এবং অন্যরা প্রতিটি শীর্ষবিন্দুর প্রতিবেশী ডিগ্রি সবই ভিন্ন এমন গ্রাফ অধ্যয়ন করেছেন
3. স্থানীয়ভাবে অনিয়মিত গ্রাফ 2,12:
   • Karoński, Luczak, Thomason 1-2-3 অনুমান প্রস্তাব করেছেন (সম্প্রতি Keusch দ্বারা সমাধান করা হয়েছে 13)
   • Baudon এবং অন্যরা নিয়মিত গ্রাফকে স্থানীয়ভাবে অনিয়মিত সাবগ্রাফে বিয়োজন অধ্যয়ন করেছেন

মুছে ফেলার অপারেশনের মাধ্যমে সম্পত্তি প্রবর্তন

4. নিয়মিততা প্রবর্তন 3,4:
   • Bazgan এবং অন্যরা প্রান্তিক ঘূর্ণন মাধ্যমে ডিগ্রি বেনামীকরণ অধ্যয়ন করেছেন
   • Belmonte এবং Sau বড় বিজোড় প্ররোচিত সাবগ্রাফ খোঁজা অধ্যয়ন করেছেন
5. শীর্ষবিন্দু অনিয়মিততা সাবগ্রাফ 11:
   • Fioravantes এবং অন্যরা শীর্ষবিন্দু মুছে ফেলার মাধ্যমে স্থানীয় অনিয়মিততা অর্জন প্রবর্তন করেছেন
   • গাছের প্রস্থ এবং সর্বোচ্চ ডিগ্রি সম্পর্কে FPT অ্যালগরিদম প্রমাণ করেছেন
6. প্রান্তিক অনিয়মিততা সাবগ্রাফ 10:
   • সম্প্রতি প্রবর্তিত ধারণা (এই কাগজের সরাসরি পূর্বসূরী)
   • NP-কঠোরতা এবং একাধিক W1-কঠোর ফলাফল প্রমাণ করেছেন

এই কাগজের অনন্য অবদান

সম্পর্কিত কাজের তুলনায়:

• প্রথমবার k+∆ এবং শীর্ষবিন্দু কভার সংখ্যা সম্পর্কে FPT অ্যালগরিদম প্রস্তাব করুন
• প্রথমবার একাধিক গ্রাফ শ্রেণীর সঠিক মান সিস্টেমেটিকভাবে অধ্যয়ন করুন
• প্রথমবার m/3+c অনুমান প্রস্তাব করুন এবং ব্যাপকভাবে যাচাই করুন
• সম্পূর্ণ গ্রাফ গভীরভাবে অধ্যয়ন করুন, ঘন গ্রাফ প্যারামিটার বোঝার ভিত্তি স্থাপন করুন

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

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

1. অ্যালগরিদম স্তর: যদিও সমস্যাটি একাধিক প্যারামিটারে W1-কঠোর, সমন্বিত প্যারামিটার (k+∆) বা কাঠামোগত প্যারামিটার (শীর্ষবিন্দু কভার সংখ্যা) এর মাধ্যমে FPT অ্যালগরিদম পাওয়া যায়
2. কাঠামো স্তর:
   • একাধিক গ্রাফ শ্রেণীর Ie(G) সঠিকভাবে নির্ধারণ বা কঠোরভাবে সীমাবদ্ধ করা যায়
   • গাছ এবং বিরল গ্রাফের আচরণ তুলনামূলকভাবে সহজ
   • সম্পূর্ণ গ্রাফ ত্রিভুজ সংখ্যার সাথে সম্পর্কিত সূক্ষ্ম কাঠামো প্রদর্শন করে
3. তাত্ত্বিক স্তর: অনুমান 1 যদি সত্য হয়, তাহলে Ie(G) এর অ্যাসিম্পটোটিক আচরণ একীভূত করবে

সীমাবদ্ধতা

1. সম্পূর্ণ গ্রাফের অসম্পূর্ণতা: শুধুমাত্র ত্রিভুজ সংখ্যার ক্রমের ক্ষেত্রে সমাধান করা হয়েছে, সাধারণ সম্পূর্ণ গ্রাফ Kn এর সঠিক মান এখনও অজানা
2. অনুমান 1 এর ধ্রুবক: যদিও একাধিক গ্রাফ শ্রেণীতে যাচাই করা হয়েছে, কিন্তু ধ্রুবক c এর সঠিক মান এবং সাধারণ প্রমাণ এখনও অনুপস্থিত
3. অ্যালগরিদম দক্ষতা:
   • k+∆ এর FPT অ্যালগরিদম ∆^(2k) এর উপর সূচকীয় নির্ভরতা, ব্যবহারিক প্রয়োগ সীমিত
   • শীর্ষবিন্দু কভার অ্যালগরিদম যদিও ILP পদ্ধতি উন্নত করেছে, তবুও 2^O(vc^4) নির্ভরতা রয়েছে
4. ঘন গ্রাফ প্যারামিটার: প্রতিবেশী বৈচিত্র্য, ক্লিকের দূরত্ব ইত্যাদি প্যারামিটারের FPT সম্পত্তি এখনও অমীমাংসিত

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

লেখকরা স্পষ্টভাবে প্রস্তাবিত দিকনির্দেশনা:

1. গতিশীল দ্বন্দ্ব প্যারামিটার: স্থির conf প্যারামিটার উন্নত করুন যাতে গতিশীলভাবে দ্বন্দ্ব বিবর্তন ক্যাপচার করা যায়
2. সম্পূর্ণ গ্রাফ এবং ঘন গ্রাফ:
   • সাধারণ সম্পূর্ণ গ্রাফ Kn এর Ie সঠিক মান নির্ধারণ করুন
   • ঘন গ্রাফের সীমা কঠোর করুন
3. k-অবক্ষয়ী গ্রাফে সম্প্রসারণ: অনুরূপ কৌশল ব্যবহার করে (k-1)n + ⌊n/3⌋ এর উপরের সীমা পান
4. গাছের প্রস্থ প্যারামিটারকরণ: সাহিত্য 11 এর শীর্ষবিন্দু সংস্করণ অ্যালগরিদম প্রান্তিক সংস্করণে খাপ খাইয়ে নেওয়া উচিত
5. প্রতিবেশী বৈচিত্র্য: সম্পূর্ণ গ্রাফ সমস্যা সমাধানের পরে সম্পূর্ণভাবে সমাধান করা প্রয়োজন

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

শক্তি

1. তাত্ত্বিক গভীরতা:
   • প্রমাণ কৌশল পরিশীলিত, বিশেষত লেমা 1 এর দূরত্ব সীমাবদ্ধতা এবং গাছের আবেগপ্রবণ প্রমাণ
   • কার্নেলাইজেশন অ্যালগরিদম প্যারামিটারযুক্ত জটিলতার গভীর বোঝাপড়া প্রদর্শন করে
   • সম্পূর্ণ গ্রাফের ত্রিভুজ সংখ্যা ফলাফল গভীর সমন্বয় কাঠামো প্রকাশ করে
2. সিস্টেমেটিকতা:
   • বিরল থেকে ঘন পর্যন্ত একাধিক গ্রাফ শ্রেণী কভার করে
   • অ্যালগরিদম ফলাফল এবং কাঠামো ফলাফল উভয়ই অন্তর্ভুক্ত
   • তাত্ত্বিক বিশ্লেষণ এবং গঠনমূলক প্রমাণ সমন্বিত
3. অনুমান প্রস্তাব:
   • অনুমান 1 শক্তিশালী একীভূতকরণ এবং অনুপ্রেরণামূলক
   • একাধিক গ্রাফ শ্রেণীতে যাচাইকরণ বিশ্বাসযোগ্যতা বৃদ্ধি করে
   • উপপাদ্য 1 1/3 সহগের কঠোরতা প্রমাণ করে
4. লেখার গুণমান:
   • কাঠামো স্পষ্ট, সহজ থেকে জটিল ক্রমান্বয়ে উন্নত
   • প্রমাণ বিস্তারিত কিন্তু অপ্রয়োজনীয় নয়
   • চিত্র বোঝা সহায়তা করে (যেমন চিত্র 3, চিত্র 4)
5. ব্যবহারিক অ্যালগরিদম:
   • গাছের O(n∆^3) অ্যালগরিদম বহুপদ সময় জটিলতা রয়েছে
   • FPT অ্যালগরিদম ব্যবহারিক প্রয়োগের জন্য তাত্ত্বিক গ্যারান্টি প্রদান করে

দুর্বলতা

1. সম্পূর্ণতা ফাঁক:
   • সম্পূর্ণ গ্রাফের সাধারণ ক্ষেত্র অমীমাংসিত, ঘন গ্রাফ বোঝা সীমিত করে
   • অনুমান 1 সাধারণ প্রমাণ অনুপস্থিত
2. অ্যালগরিদম ব্যবহারিকতা:
   • k+∆ অ্যালগরিদম এর দ্বিগুণ সূচকীয় নির্ভরতা ব্যবহারিক প্রয়োগ সীমিত করে
   • অ্যালগরিদম ব্যবহারিক কর্মক্ষমতা কোন পরীক্ষামূলক মূল্যায়ন নেই
3. ধ্রুবক অপ্টিমাইজেশন:
   • উপপাদ্য 12 এর সীমা ⌊m/2⌋+n+∆-2 সম্ভবত কঠোর নয়
   • বিভিন্ন গ্রাফ শ্রেণীর ধ্রুবক c মান সঠিকভাবে নির্ধারিত হয়নি
4. নিম্ন সীমা বিশ্লেষণ:
   • conf(G)/(2∆-1) ছাড়া, আরও সূক্ষ্ম নিম্ন সীমা কৌশল অনুপস্থিত
   • আনুমানিক অ্যালগরিদম আলোচনা নেই
5. প্যারামিটার শ্রেণীবিভাগ:
   • FPT এবং W1-কঠোরের মধ্যে সীমানা সম্পূর্ণভাবে চিহ্নিত করা হয়নি
   • নির্দিষ্ট প্রাকৃতিক প্যারামিটার (যেমন গাছের প্রস্থ+∆) অন্বেষণ করা হয়নি

প্রভাব

1. তাত্ত্বিক অবদান:
   • প্রান্তিক অনিয়মিততা সাবগ্রাফ গবেষণার জন্য দৃঢ় ভিত্তি স্থাপন করে
   • অনুমান 1 যদি সত্য হয় তাহলে গুরুত্বপূর্ণ সমন্বয় ফলাফল হবে
   • পদ্ধতি (বিশেষত লেমা 1) অন্যান্য গ্রাফ সংশোধন সমস্যায় প্রয়োগযোগ্য হতে পারে
2. পরবর্তী গবেষণা:
   • সম্পূর্ণ গ্রাফ সমস্যা সমন্বয়বাদীদের মনোযোগ আকর্ষণ করবে
   • FPT অ্যালগরিদম কৌশল অন্যান্য স্থানীয় সম্পত্তিতে সাধারণীকরণ করা যায়
   • গ্রাফের স্থানীয় অনিয়মিততা বোঝার জন্য নতুন দৃষ্টিভঙ্গি প্রদান করে
3. ব্যবহারিক মূল্য:
   • গাছ অ্যালগরিদম নেটওয়ার্ক বিশ্লেষণে সরাসরি প্রয়োগ করা যায়
   • গ্রাফ বেনামীকরণ, নেটওয়ার্ক স্থিতিস্থাপকতা ইত্যাদি প্রয়োগের জন্য তাত্ত্বিক সমর্থন প্রদান করে
4. উন্মুক্ততা:
   • স্পষ্ট এবং আকর্ষণীয় উন্মুক্ত সমস্যা রেখে যায়
   • বিভিন্ন কঠিনতা স্তর বিভিন্ন গবেষকদের জন্য উপযুক্ত

প্রযোজ্য দৃশ্যকল্প

1. নেটওয়ার্ক ডিজাইন: সংলগ্ন নোডের একই ডিগ্রি এড়ানোর প্রয়োজন এমন দৃশ্যকল্প (যেমন লোড ব্যালেন্সিং)
2. গ্রাফ বেনামীকরণ: ডিগ্রি প্যাটার্ন ভাঙতে প্রান্তিক মুছে ফেলার মাধ্যমে গোপনীয়তা রক্ষা করুন
3. তাত্ত্বিক কম্পিউটার বিজ্ঞান:
   • প্যারামিটারযুক্ত জটিলতার শিক্ষা কেস
   • গ্রাফ সংশোধন সমস্যা গবেষণার প্রতিমান
4. সমন্বয় অপ্টিমাইজেশন: আরও জটিল অপ্টিমাইজেশন সমস্যার সাবপ্রবলেম হিসাবে

মূল উদ্ধৃতি (গুরুত্বপূর্ণ রেফারেন্স)

2 Baudon et al. (2015): নিয়মিত গ্রাফকে স্থানীয়ভাবে অনিয়মিত সাবগ্রাফে বিয়োজন
6 Chartrand et al. (1988): অনিয়মিত নেটওয়ার্ক, অনিয়মিত শক্তি প্রবর্তন
10 Fioravantes et al. (2024): প্রান্তিক অনিয়মিততা সাবগ্রাফ প্রবর্তন, মৌলিক কঠিনতা ফলাফল প্রমাণ
11 Fioravantes et al. (2025): শীর্ষবিন্দু অনিয়মিততা সাবগ্রাফের জটিলতা
12 Karoński et al. (2004): 1-2-3 অনুমান
13 Keusch (2024): 1-2-3 অনুমান সমাধান

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