لم آفتابگردان

(من الآن به این نتیجه رسیدم که می‌توانم از کلمات کلیدی به جای نوشتن مبحث در عنوان استفاده کنم!)

آفتابگردان: اگر از هر مجموعه اشتراک همه‌ی مجموعه‌های ورودی را برداریم، مجزا شوند. (مرکز آفتاب گردان در همه مشترک است و گلبرگ‌ها جدا هستند)

لم (اردوش، رادو، 1960): اگر اندازه یک مجموعه از مجموعه‌ها بیشتر از 

(p-1)^d d!

باشد و فقط شامل مجموعه‌های با اندازه‌ی حداکثر d باشد، آنگاه مجموعه‌ی مجموعه‌ها دارای آفتابگردان با p گلبرگ است. همچنین این آفتابگردان در زمان چندجمله‌ای قابل پیدا کردن است.

کاهش تاج (crown reduction): الگوریتم‌های پارامتر ثابت

اگر رأسهای گراف را به مجموعه‌های C H B افراز کنیم به طوری که C یک مجموعه‌ی مستقل باشد و هیچ یالی بین C و B نباشد و بین C و H یک تطابق باشد که همه‌ی H را بپوشاند یک کاهش تاج داریم.

برای مسأله‌ی پوشش رأسی می‌توانیم C و H را از گراف حذف کنیم و k-|H| رأس دیگر پیدا کنیم چون همه‌ی C توسط H پوشش داده می‌شود. اینکه H جزو جواب بهینه است از اینجا مشخص می‌شود که رأسهای C فقط به H وصل هستند.

قضیه: اگر یک گراف بدون رأس تنها و عدد k داده شده باشد، در زمان چندجمله‌ای:

یا می‌توانیم یک تطابق با k+1 یال پیدا کنیم که نتیجه می‌دهد مسأله جواب ندارد.

یا می‌توانیم یک کاهش تاج پیدا کنیم که مسأله کوچکتر می‌شود.

یا می‌توانیم نتیجه بگیریم که گراف حداکثر 3k رأس دارد (یک کرنل 3k رأسی است). (در نتیجه می‌توانیم در نمایی بر حسب k حلش کنیم.)

نتیجه: یک کرنل 3k رأسی برای پوشش رأسی به دست می‌آید.

هسته سازی(kernelization): الگوریتم‌های پارامتر ثابت

الگوریتم پارامتر ثابت الگوریتمی است که بر اساس پارامتر ثابت نمایی است و بر اساس ورودی چندجمله‌ای است و پارامتر ثابت نمی‌تواند اندازه ورودی باشد ولی می‌تواند اندازه‌ی خروجی باشد.

هسته‌سازی یک تبدیل چندجمله‌ای است که یک نسخه از مسأله را به یک نسخه‌ی با پارامتر کوچکتر تبدیل می‌کند که اندازه‌ی این نمونه‌ی جدید از تابعی از پارامتر کمتر باشد و جواب آن تغییر نکند. (نسخه‌ی تصمیم گیری مسأله)

*اگر یک الگوریتم قابل کرنل‌سازی باشد، FPT است.

اثبات: نسخه‌ی کوچکتر بر حسب k نمایی است (چون در کرنل خود اندازه مسأله برحسب k نمایی است) پس آن را با brute force (امتحان کردن همه‌ی حالت‌ها) حل می‌کنیم.

*عکس قضیه: هر مسأله‌ی FPT دارای یک الگوریتم کرنل‌سازی است.

اثبات: حالت بندی می‌کنیم. اگر f(k)<n باشد، که مسأله چندجمله‌ای حل می‌شود و آن را حل می‌کنیم و یک نسخه‌ی بدیهی از مسأله با همان جواب را به عنوان کرنل برمی‌گردانیم.

اگر n<f(k) باشد هم خودش یک کرنل است و خودش را برمی‌گردانیم.

الگوریتم‌های پارامتری (دانشگاه استنفورد)

http://web.stanford.edu/~rrwill/cs266.html

در این درس الگوریتم‌های پارامتر ثابت و روش‌های آنها بررسی می‌شوند.