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

در اکثر مسایل ساختارهایی در داده‌ها هست که کمک می‌کند برخلاف الگوریتم‌هایی که فقط به n بستگی دارند، بدون نیاز به حل P vs. NP مسئله را حل کنیم.

مثلاً مسئله‌ی Multiple Sequence Alignment را می‌توان در O(2^n^c) حل کرد و NPC است اما در عمل پارامترهایی مانند طول، میزان تطابق، تعداد حروف الفبا می‌توانند کوچک باشند که می‌توان مسئله را در زمان زیر حل کرد:

2^N+2^|Sigma|+2^delta+2^(1/epsilon)

مسایل دو دسته هستند:

۱- پارامتر ثابت (FPT) هستند که این خودش دو نوع multiplicative (که در آن زمان f(k)n^c است) و additive (که در آن زمان f(k)+n^c است) دارد.

۲- مسایل w-hard و XP که زمان آنها n^g(k) است.

اولین بار که الگوریتم‌های پارامتر ثابت ارائه شدند همه اعتراض کردند که نمایی بر حسب k در کنار n قابل قبول نیست.

این مسئله اولین بار برای Type Checking در زبان ML استفاده شد که آنجا پی بردند که الگوریتم‌هایی که در عمل به کار می‌روند بر خلاف تحلیل تئوری آنها خوب جواب می‌دهند. این مسئله NP-hard است ولی الگوریتم پارامتر ثابت با زمان O(2^k n) دارد که در آن k عمق typeها و n طول برنامه است.

امروزه مسئله‌ی مهم‌تری مطرح است. الگوریتم RSA را یک Quantum Computer با variantای از الگوریتم Shore می‌تواند حل کند. برای RSA به ضرب دو عدد اول نیاز است. فاصله‌ی همینگ بین دو عدد اول همیشه ۱ یا ۲ است که این همان پارامتر ثابتی است که برای شکستن RSA به کار می‌آید. (یک چیزی هم در مورد فاکتور گیری اعداد نوشتم که الآن یادم نیست چی است.)

معمولاً brute force روی پارامتر می‌زنند اما برای بعضی مسایل مانند پوشش رأسی می‌شود کارهای بهتری هم کرد. روش bounded search tree را به کار می‌بریم. از یال u-v یا باید u را برداریم یا v را. پس در زمان O(2^k n) مسئله حل می‌شود.

یک چیزی در مورد minor graph algorithm.

سلسله مراتب مسایل پارامتری:

P < FPT < M[1] < W[1] <... <W[2]< ... < XP

مثالهای مسایل هم پوشش رأسی برای FPT، خوشه برای W[1]، مسئله‌ی dominating set برای w[2] است.

برای اثبات این مسایل به کاهشی نیاز داریم که پارامتر را کنترل می‌کند. برای سلسله مراتبی که گفته شد، مثلاً ثابت کرده‌اند که اگر dominating set پارامتر ثابت باشد، clique (خوشه) هم پارامتر ثابت است.

به جای قضیه‌ی cook-levin از قضیه‌ی k-step halting problem استفاده می‌کنند تا w[1] را تعریف کنند. k-clique هم برای w[1] کامل است. (w[1]-complete)

* روش bounded tree width

یک ویژگی مسئله است. مثلاً یک سری از رأس‌ها متناظر متغیرها و یک سری دیگر متناظر عبارت‌ها باشند. مثلاً control flow برنامه‌های ساختیافته. (پشته)

این مسئله را می‌شود با sliding window حل کرد چون یالهای آن دور ندارد.  یعنی حداکثر تعداد مقادیری که باید بدانیم تا مرحله‌ی بعدی را بفهمیم کم است. می‌توانیم مثلاً با یک dfs یالهای کوتاه بعدی را پیدا کنیم.

ایده‌ی این روش شکستن ورودی به قطعات کوچکتر است.

در یک بعد نمی‌شود این کار را کرد چون تهش چیزی نمی‌ماند. اما با چند پارامتر می‌شود.

* مسئله‌ی Karsten's trains

یک مجموعه قطار داریم و یک مجموعه ایستگاه داریم و هر قطار یک سری ایستگاه را پوشش می‌دهد. (گراف دوبخشی کامل)

برای چنین مسئله‌ای می‌توانیم قطارهایی را که ایستگاه‌هایشان تماماً زیرمجموعه‌ی یک قطار دیگر است حذف کنیم.

{تا جایی که من می‌دانم این کار را kernelization می‌گویند که بخواهیم اندازه‌ی مسئله را با ساده‌سازی کم کنیم.}

*روشی برای فهمیدن اینکه کرنل با اندازه‌ی چندجمله‌ای وجود دارد یا خیر:

پوشش رأسی و خوشه دوگان یکدیگر هستند. {احتمالاً از نظر اندازه‌ی پارامتر که سایز خروجی است.}

{اشاره‌ی نامعلومی به اسم lanston}

مقایسه‌ی f(k) با اندازه‌ی کرنل.

یک پیش پردازش می‌کنیم تا به کوچکترین مسئله‌ی ممکن برسیم. {این را می‌دانم تعریف kernelization است.}

-cygan, fomina, ...

-multivariate

-fpt newsletter

*مسئله‌ی زمانبندی حساس به گرما (heat sensitive scheduling) که np-hard است در نظر بگیرید. معمولاً گرما یک عدد نیست بلکه بیشتر یک رتبه‌بندی است (مثلاً خیلی سرد، سرد، معمولی، گرم، خیلی گرم) که باعث می‌شود بتوانیم آن را پارامتر بگیریم. که به ما یک الگوریتم پارامتر ثابت می‌دهد.

*رنگ‌آمیزی گراف: حریصانه رنگ کن و اگر از k رنگ بیشتر شد برگرد و با یک روش دیگر رنگ کن.

* تعریف استقرایی عرض درختی (tree-width)

k-graph: افراز رأسها به k مجموعه که عرض هر کدام محدود است.

۱- disjoint union

۲- renaming

۳- fusion

* عرض خوشه (clique width)

۱- مثل قبلی

۲- مثل قبلی

۳- بین ui و uj همه‌ی یالها را می‌سازید (گراف دوبخشی کامل).

cw(G) <= 2^(tw(G)+1)+1

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