2025-11-21T03:46:15.611457

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach

Clinch, Gaspers, He et al.

This work introduces two techniques for the design and analysis of branching algorithms, illustrated through the case study of the Vertex Cover problem. First, we present a method for automatically generating branching rules through a systematic case analysis of local structures. Second, we develop a new technique for analyzing randomized branching algorithms using the Measure & Conquer method, offering greater flexibility in formulating branching rules. By combining these innovations with additional techniques, we obtain the fastest known randomized algorithms in different parameters for the Vertex Cover problem on graphs with bounded degree (up to 6) and on general graphs. For example, our algorithm solves Vertex Cover on subcubic graphs in $O^*(1.07625^n)$ time and $O^*(1.13132^k)$ time, respectively. For graphs with maximum degree 4, we achieve running times of $O^*(1.13735^n)$ and $O^*(1.21103^k)$, while for general graphs we achieve $O^*(1.25281^k)$.

academic

দ্রুততর র‍্যান্ডমাইজড ভার্টেক্স কভার অ্যালগরিদম: একটি স্বয়ংক্রিয় পদ্ধতি

মৌলিক তথ্য

পেপার আইডি: 2510.09027
শিরোনাম: A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
লেখক: Katie Clinch (University of Queensland), Serge Gaspers (UNSW Sydney), Tao Zixu He (University of Massachusetts Amherst), Simon Mackenzie (UNSW Sydney), Tiankuang Zhang (UNSW Sydney)
শ্রেণীবিভাগ: cs.DS (ডেটা স্ট্রাকচার এবং অ্যালগরিদম), cs.CC (কম্পিউটেশনাল জটিলতা)
প্রকাশনার সময়: ২০২৫
পেপার লিংক: https://arxiv.org/abs/2510.09027

সারসংক্ষেপ

এই পেপারটি ভার্টেক্স কভার সমস্যার জন্য শাখা অ্যালগরিদম ডিজাইন এবং বিশ্লেষণের দুটি নতুন কৌশল উপস্থাপন করে। প্রথমত, সিস্টেমেটিক স্থানীয় কাঠামো কেস বিশ্লেষণের মাধ্যমে স্বয়ংক্রিয়ভাবে শাখা নিয়ম তৈরি করার একটি পদ্ধতি প্রস্তাব করা হয়েছে। দ্বিতীয়ত, Measure & Conquer পদ্ধতি ব্যবহার করে র‍্যান্ডমাইজড শাখা অ্যালগরিদম বিশ্লেষণের একটি নতুন কৌশল উন্নত করা হয়েছে, যা শাখা নিয়ম প্রণয়নে আরও বেশি নমনীয়তা প্রদান করে। এই উদ্ভাবনগুলি অন্যান্য কৌশলের সাথে একত্রিত করে, সীমাবদ্ধ ডিগ্রি গ্রাফ (সর্বোচ্চ ডিগ্রি ৬) এবং সাধারণ গ্রাফে ভার্টেক্স কভার সমস্যার দ্রুততম পরিচিত র‍্যান্ডমাইজড অ্যালগরিদম অর্জন করা হয়েছে। উদাহরণস্বরূপ, অ্যালগরিদম ত্রিঘাত গ্রাফে $O^*(1.07625^n)$ এবং $O^*(1.13132^k)$ চলার সময় অর্জন করে, সর্বোচ্চ ডিগ্রি ৪ এর গ্রাফে $O^*(1.13735^n)$ এবং $O^*(1.21103^k)$ চলার সময় অর্জন করে, এবং সাধারণ গ্রাফে $O^*(1.25281^k)$ অর্জন করে।

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

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

ভার্টেক্স কভার সমস্যা কম্পিউটার বিজ্ঞানের সবচেয়ে ক্লাসিক NP-সম্পূর্ণ সমস্যাগুলির মধ্যে একটি, যা ৫০ বছরেরও বেশি সময় ধরে অধ্যয়ন করা হয়েছে। গ্রাফ $G = (V, E)$ এবং পূর্ণসংখ্যা $k$ দেওয়া হলে, এটি নির্ধারণ করতে হবে যে আকার সর্বাধিক $k$ এর একটি ভার্টেক্স সাবসেট $C \subseteq V$ বিদ্যমান কিনা যা সমস্ত প্রান্ত কভার করে। এই সমস্যাটি তাত্ত্বিক কম্পিউটার বিজ্ঞান এবং ব্যবহারিক প্রয়োগ উভয় ক্ষেত্রেই গুরুত্বপূর্ণ।

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

হাতে তৈরি ডিজাইনের সীমাবদ্ধতা: নির্ভুল শাখা অ্যালগরিদম যদিও NP-কঠিন সমস্যা সমাধানের সবচেয়ে কার্যকর সরঞ্জামগুলির মধ্যে একটি, তবুও প্রধানত হাতে তৈরি করা হয়, প্রতিটি নতুন সমস্যার জন্য কাস্টমাইজড কেস বিশ্লেষণ এবং সাবধানে সমন্বিত পরিমাপ প্রয়োজন।
দুর্বল পোর্টেবিলিটি: এই হাতে তৈরি প্রক্রিয়া অ্যালগরিদমের পোর্টেবিলিটি সীমাবদ্ধ করে এবং গবেষণার অগ্রগতি হ্রাস করে।
অপর্যাপ্ত র‍্যান্ডমাইজেশন বিশ্লেষণ: বিদ্যমান Measure & Conquer পদ্ধতি প্রধানত নির্ধারক অ্যালগরিদমের জন্য ব্যবহৃত হয়, র‍্যান্ডমাইজড শাখা অ্যালগরিদমের জন্য সিস্টেমেটিক বিশ্লেষণ পদ্ধতির অভাব রয়েছে।

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

এই পেপারটি যুক্তি দেয় যে শাখা অ্যালগরিদম ডিজাইনের বেশিরভাগ কাজ স্বয়ংক্রিয় করা যায়, এবং একটি কাঠামো প্রস্তাব করে যা:

সিস্টেমেটিকভাবে স্থানীয় কনফিগারেশন অন্বেষণ করে
সমতুল্য ক্লাস একত্রিত করে অনুসন্ধান সরল করে
সরাসরি পরিমাপ অগ্রগতি অপ্টিমাইজ করে এমন LP/ILP সূত্র সমাধান করে উচ্চ মানের নির্ধারক বা র‍্যান্ডমাইজড শাখা নিয়ম তৈরি করে

মূল অবদান

র‍্যান্ডমাইজড Measure & Conquer: র‍্যান্ডমাইজড অ্যালগরিদমের চলার সময় বিশ্লেষণ করার জন্য Measure & Conquer প্রসারিত করে, M&C কে সম্ভাব্য শাখা নিয়ম কার্যকরভাবে পরিচালনা করতে সক্ষম করে।
LP/ILP-ভিত্তিক স্বয়ংক্রিয় নিয়ম প্রজন্ম: নিয়ম নির্বাচন এবং ওজন বরাদ্দকে সরাসরি পরিমাপ হ্রাস সর্বাধিক করে এমন অপ্টিমাইজেশন সমস্যা হিসাবে প্রবর্তন করে একটি উপন্যাস কাঠামো প্রবর্তন করে, যা স্বাভাবিকভাবে নির্ধারক এবং র‍্যান্ডমাইজড নিয়ম উভয়কে সমর্থন করে।
ভার্টেক্স কভার সমস্যার উন্নত চলার সময়: উৎপাদিত অ্যালগরিদম সাধারণ গ্রাফ এবং বিভিন্ন সীমাবদ্ধ ডিগ্রি পরিস্থিতিতে সর্বোত্তম পরিচিত প্যারামিটারাইজড সীমানা উন্নত করে, যার মধ্যে রয়েছে:
- ত্রিঘাত গ্রাফ: $O^*(1.07625^n)$ এবং $O^*(1.13132^k)$
- ডিগ্রি ৪ গ্রাফ: $O^*(1.13735^n)$ এবং $O^*(1.21103^k)$
- সাধারণ গ্রাফ: $O^*(1.25281^k)$

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

কাজের সংজ্ঞা

ভার্টেক্স কভার সমস্যা: একটি অনির্দেশিত গ্রাফ $G = (V, E)$ এবং অ-নেতিবাচক পূর্ণসংখ্যা $k$ দেওয়া হলে, নির্ধারণ করুন যে একটি ভার্টেক্স সাবসেট $C \subseteq V$ বিদ্যমান কিনা যেখানে $|C| \leq k$ , যেমন $C$ সমস্ত প্রান্ত কভার করে (অর্থাৎ প্রতিটি প্রান্তের কমপক্ষে একটি শেষবিন্দু $C$ -তে রয়েছে)।

মূল প্রযুক্তিগত কাঠামো

১. র‍্যান্ডমাইজড Measure & Conquer

লেম্মা ২: ধরুন $A_r$ সিদ্ধান্ত সমস্যা $\Pi$ এর একটি র‍্যান্ডমাইজড শাখা অ্যালগরিদম, এবং $\mu(\cdot)$ হল $\Pi$ উদাহরণের একটি অ-নেতিবাচক পরিমাপ। যেকোনো উদাহরণ $I$ এর জন্য, $A_r$ হয় $\mu(I) = 0$ হলে ধ্রুবক সময়ে $I$ সমাধান করে, অথবা $I$ কে সংশ্লিষ্ট ওজন $w_1, \ldots, w_k$ সহ সাব-উদাহরণ $I_1, \ldots, I_k$ এ হ্রাস করে।

মূল সীমাবদ্ধতা শর্ত: $\sum_{i=1}^k w_i \cdot 2^{\mu(I_i)} \leq 2^{\mu(I)}$

সাব-উদাহরণ $I_i$ কমপক্ষে $w_i \cdot 2^{\mu(I_i)-\mu(I)}$ সম্ভাবনার সাথে র‍্যান্ডমলি নির্বাচিত হয়।

২. স্থানীয় কনফিগারেশন এবং সম্প্রসারণ কভার

সংজ্ঞা ৩ (স্থানীয় কনফিগারেশন): ভার্টেক্স কভার সমস্যার স্থানীয় কনফিগারেশন টাপল $L = (H, D)$ হিসাবে সংজ্ঞায়িত করা হয়, যেখানে $H = (V, E)$ একটি গ্রাফ, এবং $D$ প্রতিটি ভার্টেক্সকে এর সম্পর্কিত অসম্পূর্ণ প্রান্তের সংখ্যায় ম্যাপ করে।

অ্যালগরিদম ২ (সম্প্রসারণ অ্যালগরিদম):

সর্বনিম্ন ডিগ্রি এবং সর্বনিম্ন অসম্পূর্ণ প্রান্ত সহ সীমানা ভার্টেক্স $v$ নির্বাচন করুন
প্রতিটি $u_i \in \delta(L) \setminus \{v\}$ এর জন্য, $v-u_i$ সংযোগ করে এমন একটি নতুন স্থানীয় কনফিগারেশন তৈরি করুন
প্রতিটি $i \in \{1, \ldots, \Delta\}$ এর জন্য, ডিগ্রি $i$ এর একটি নতুন ভার্টেক্স $u$ যোগ করুন এবং এটি $v$ এর সাথে সংযুক্ত করুন

३. পরিমাপ ডিজাইন

পরিমাপ ব্যবহার করুন: $\mu = \alpha k + \beta_1 n_1 + \beta_2 n_2 + \beta_3 n_3$

যেখানে $k$ ভার্টেক্স কভারের আকার, $n_i$ ডিগ্রি $i$ এর ভার্টেক্সের সংখ্যা প্রতিনিধিত্ব করে, এবং $\alpha, \beta_1, \beta_2, \beta_3$ ওজন।

সীমাবদ্ধতা শর্ত:

প্যারামিটার $n$ এর জন্য অ্যালগরিদম: $\alpha = 0$ এবং $\beta_3 \geq 0$ , $0 \leq \frac{3\beta_1}{4} \leq \frac{3\beta_2}{4} \leq \beta_3$ পান
প্যারামিটার $k$ এর জন্য অ্যালগরিদম: $\beta_i \leq 0$ ( $i \in \{1,2\}$ ) এবং $\beta_3 = 0$

४. শাখা নিয়ম প্রজন্ম

রৈখিক প্রোগ্রামিং সূত্র: $\min_w \sum_{b_i \in B} w_i \cdot \text{cost}(L, b_i)$ $\text{s.t. } \forall R_i \in \mathcal{R} \sum_{b_j \in B: R_i \in EB(L,b_j,\mathcal{R})} w_j \geq 1$ $\forall b_i \in B: w_i \in [0,1]$

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

প্রান্ত-কেন্দ্রিক সম্প্রসারণ: পূর্ববর্তী ভার্টেক্স-দ্বারা-ভার্টেক্স সম্প্রসারণের বিপরীতে, প্রান্ত-দ্বারা-প্রান্ত সম্প্রসারণ কনফিগারেশন গ্রহণ করে, প্রার্থী কনফিগারেশনের সংখ্যা উল্লেখযোগ্যভাবে হ্রাস করে।
অপ্রয়োজনীয়তা নিয়ন্ত্রণ: উদাহরণ স্থান বিভাজন এবং সমরূপী স্থানীয় কনফিগারেশন একত্রিত করার মাধ্যমে সদৃশ নির্মূল করে, ঘন ঘন সাবগ্রাফ আইসোমরফিজম প্রশ্নের ওভারহেড এড়ায়।
একীভূত অপ্টিমাইজেশন কাঠামো: নিয়ম নির্বাচন এবং ওজন বরাদ্দকে একক LP/ILP অপ্টিমাইজেশন সমস্যা হিসাবে প্রকাশ করে, সরাসরি পরিমাপ অগ্রগতি সর্বাধিক করে, র‍্যান্ডমাইজড শাখা নির্বিঘ্নে সমর্থন করে।

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

পরীক্ষার পরিবেশ

দুটি পরিমাপ ব্যবহার করুন: $\mu_1 = 0.106n_3$ (প্যারামিটার $n$ ) এবং $\mu_2 = 0.178k - 0.0445n_1 - 0.089n_2$ (প্যারামিটার $k$ )
ত্রিঘাত গ্রাফের উদাহরণ স্থান অপ্টিমাইজেশনের জন্য ১৯টি সাব-স্পেসে বিভক্ত করুন
গ্রাফ আইসোমরফিজম সনাক্তকরণের জন্য Nauty লাইব্রেরি ব্যবহার করুন, রৈখিক প্রোগ্রামিং সমাধানকারীর জন্য ALGLIB ব্যবহার করুন

সরলীকরণ নিয়ম

৫টি সরলীকরণ নিয়ম বাস্তবায়ন করা হয়েছে:

বিচ্ছিন্ন ভার্টেক্স নিয়ম
ডিগ্রি ১ ভার্টেক্স নিয়ম
ডিগ্রি ২ ত্রিভুজ নিয়ম
ডিগ্রি ২ চেইন নিয়ম
বিকল্প চক্র নিয়ম

তুলনা বেঞ্চমার্ক

নিম্নলিখিত সর্বশেষ ফলাফলের সাথে তুলনা করুন:

ত্রিঘাত গ্রাফ: Xiao & Nagamochi এর $O^*(1.08351^n)$ এবং $O^*(1.14416^k)$
ডিগ্রি ৪ গ্রাফ: Xiao & Nagamochi এর $O^*(1.13760^n)$ এবং $O^*(1.21131^k)$
সাধারণ গ্রাফ: Harris & Narayanaswamy এর $O^*(1.25284^k)$

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

প্রধান ফলাফল

সর্বোচ্চ ডিগ্রি	প্যারামিটার	নতুন সীমানা	পূর্ববর্তী সীমানা
∆ ≤ 3	n	$O^*(1.07625^n)$	$O^*(1.08351^n)$
	k	$O^*(1.13132^k)$	$O^*(1.14416^k)$
∆ ≤ 4	n	$O^*(1.13735^n)$	$O^*(1.13760^n)$
	k	$O^*(1.21103^k)$	$O^*(1.21131^k)$
∆ ≤ 5	k	$O^*(1.24382^k)$	$O^*(1.24394^k)$
∆ ≤ 6	k	$O^*(1.25210^k)$	$O^*(1.25214^k)$
সাধারণ গ্রাফ	k	$O^*(1.25281^k)$	$O^*(1.25284^k)$

প্রযুক্তিগত অর্জন

ত্রিঘাত গ্রাফের উল্লেখযোগ্য উন্নতি: প্যারামিটার $n$ এবং $k$ উভয়েই উল্লেখযোগ্য উন্নতি অর্জন করা হয়েছে
ডিগ্রি ৪ গ্রাফের উন্নতি: উন্নত ত্রিঘাত গ্রাফ অ্যালগরিদমকে সাব-রুটিন হিসাবে ব্যবহার করে উন্নতি অর্জন করা হয়েছে
সাধারণ গ্রাফের উন্নতি: Harris-Narayanaswamy কাঠামোতে একীভূত করে উন্নতি অর্জন করা হয়েছে

পদ্ধতি যাচাইকরণ

লেম্মা ১৯ এর মাধ্যমে উন্নতির কার্যকারিতা যাচাই করা হয়েছে: $d = \frac{2c(a+b)}{a+2c}$ যেখানে $c$ নির্ভুল অ্যালগরিদমের সূচক, $a,b$ হল FPT অ্যালগরিদম পরিমাপের সহগ।

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

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

হাতে তৈরি শাখা ডিজাইনকে অনুসন্ধান অপ্টিমাইজেশন পাইপলাইনে সফলভাবে রূপান্তরিত করা হয়েছে
বিশ্লেষণ দিক থেকে, র‍্যান্ডমাইজড শাখায় Measure & Conquer প্রসারিত করে, সম্ভাব্য নির্বাচনের সময় চলার সময় উপরের সীমার জন্য একটি নীতিগত পদ্ধতি প্রদান করে
নিয়ম প্রজন্ম দিক থেকে, শাখা আবিষ্কার এবং ওজন বরাদ্দকে সরাসরি পরিমাপ অগ্রগতি অপ্টিমাইজ করে এমন LP/ILP উদ্দেশ্য হিসাবে প্রকাশ করে

সীমাবদ্ধতা

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

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

স্বয়ংক্রিয় ওজন সমন্বয়: কনফিগারেশন সম্প্রসারণের সময় স্বয়ংক্রিয়ভাবে ওজন সমন্বয় করুন
উচ্চ ডিগ্রি গ্রাফ পরিচালনা: উচ্চতর ডিগ্রি গ্রাফ পরিচালনার জন্য বুদ্ধিমান কৌশল উন্নয়ন করুন
বিস্তৃত প্রয়োগ: কাঠামো সাবসেট সমস্যার বিস্তৃত পরিসরে প্রয়োগ করুন

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

সুবিধা

তাত্ত্বিক উদ্ভাবন: র‍্যান্ডমাইজড Measure & Conquer একটি গুরুত্বপূর্ণ তাত্ত্বিক ফাঁক পূরণ করে
পদ্ধতি সিস্টেমেটিকতা: কনফিগারেশন প্রজন্ম থেকে নিয়ম অপ্টিমাইজেশন পর্যন্ত একটি সম্পূর্ণ স্বয়ংক্রিয় কাঠামো প্রদান করে
ব্যবহারিক মূল্য: একাধিক গুরুত্বপূর্ণ সমস্যা উদাহরণে সর্বোত্তম পরিচিত ফলাফল অর্জন করে
স্কেলেবিলিটি: কাঠামো মডুলার ডিজাইন, অন্যান্য সমস্যায় স্বাধীনভাবে প্রয়োগ করা যায়

অপূর্ণতা

জটিলতা: কাঠামো বাস্তবায়ন তুলনামূলকভাবে জটিল, সামঞ্জস্যের জন্য বিশেষজ্ঞ জ্ঞান প্রয়োজন
প্রয়োগের পরিসর: প্রধানত স্থানীয় কাঠামো সহ সমস্যার জন্য প্রযোজ্য
গণনা খরচ: LP/ILP সমাধান একটি বাধা হতে পারে

প্রভাব

তাত্ত্বিক অবদান: র‍্যান্ডমাইজড শাখা অ্যালগরিদম বিশ্লেষণের জন্য নতুন সরঞ্জাম প্রদান করে
ব্যবহারিক মূল্য: শাখা অ্যালগরিদম ডিজাইনে মানব প্রচেষ্টা উল্লেখযোগ্যভাবে হ্রাস করে
পুনরুৎপাদনযোগ্যতা: খোলা উৎস বাস্তবায়ন প্রদান করে, যাচাইকরণ এবং সম্প্রসারণ সহজ করে

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

সাবসেট সমস্যা: সীমাবদ্ধ স্থানীয় মিথস্ক্রিয়া সহ সাবসেট সমস্যা
গ্রাফ সমস্যা: বিশেষত ডিগ্রি সীমাবদ্ধতা সহ গ্রাফ সমস্যা
প্যারামিটারাইজড অ্যালগরিদম: নির্ভুল সূচক অ্যালগরিদম প্রয়োজন এমন প্যারামিটারাইজড সমস্যা

সংদর্ভ

পেপারটি ২৪টি গুরুত্বপূর্ণ সংদর্ভ উদ্ধৃত করে, যা প্যারামিটারাইজড অ্যালগরিদম, নির্ভুল অ্যালগরিদম, স্বয়ংক্রিয় অ্যালগরিদম প্রজন্ম এবং অন্যান্য সম্পর্কিত ক্ষেত্রের ক্লাসিক কাজ অন্তর্ভুক্ত করে, গবেষণার জন্য একটি দৃঢ় তাত্ত্বিক ভিত্তি প্রদান করে।

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