الگوریتم‌های پارامتری (کتاب)

http://parameterized-algorithms.mimuw.edu.pl/
(منظورشان از پارامتری هم پارامتر ثابت است فقط)

On the Local Structure of Stable Clustering Instances

https://arxiv.org/pdf/1701.08423.pdf

تمرین اول کلاس تحلیل‌های ماورای بدترین حالت

لینک تمرین: http://timroughgarden.org/f14/hw/hw1.pdf

تمرینات جلسه ۱

۱- زیرمجموعه‌ای از حالت‌های الگوریتم B را در نظر بگیرید که هر کدام به ترتیب یک جایگشت خاص از اندیس‌ها مسئله را حل می‌کنند. یعنی به ترتیب آن جایگشت اندیس‌های آرایه را برای پیدا کردن عنصر مورد نظر شما چک می‌کنند. مثلاً اگر همانی باشد جستجوی خطی است. به ازای هر عنصری، یکی از این الگوریتم‌ها آن را در زمان ۱ پیدا می‌کند چون اولین مقایسه‌ای که انجام می‌دهد با آن عنصر است. از آنجا که c ثابت است پس الگوریتم A باید در زمان ثابت به ازای هر عنصری این کار را انجام دهد. یعنی در بدترین حالت هم زمان آن O(1) می‌شود، در حالی که کران پایین پیدا کردن عنصر در مدل مقایسه‌ای log n است. (اثبات این موضوع مثلاً از طریق درخت تصمیم جبری امکان پذیر است). پس به تناقض رسیدیم و الگوریتم A با این مشخصات نیست.

۲- مشابه قسمت قبل عمل می‌کنیم و الگوریتم B را هم به ازای هر جایگشت ورودی در نظر می‌گیریم که اول آن جایگشت را چک می‌کند و اگر نشد مرتب‌سازی را به یکی از روش‌های متداول انجام می‌دهد. پس هم یک الگوریتم مرتب‌سازی است و هم به ازای هر ورودی، یکی از این الگوریتم‌ها هست که آن را در زمان O(n) حل کند. پس اگر الگوریتم بهینه مصداقی (instance optimal) برای آن وجود داشته باشد، باید مرتب‌سازی را در زمان O(n) حل کند. در حالی که مرتب‌سازی در مدل مقایسه‌ای به حداقل n log n مقایسه نیاز دارد. پس به تناقض رسیدیم و چنین الگوریتمی وجود ندارد.

Fixed-Parameter Algorithms for (k, r)-Center in Planar Graphs and Map Graphs

http://www-math.mit.edu/~hajiagha/mapgraphsTALG.pdf

الگوریتم‌های پارامتر ثابت (مدرسه زمستانی هندسه محاسباتی)

http://wscg.aut.ac.ir/wscg8/images/Downloads/SeminarPresentations/WSCG8_Seminar_KhodaKarami.pdf
خوبی این ارائه این است که همه‌ی روشها را روی یک مسئله توضیح داده است.

Fixed Parameter hardness in opt

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.696.250&rep=rep1&type=pdf

جهت‌های جدید در الگوریتم‌های پارامتری (کنفرانس 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

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

SCHOOL ON PARAMETERIZED ALGORITHMS AND COMPLEXITY

http://fptschool.mimuw.edu.pl/

فشرده‌سازی بازگشتی و ماینورهای گراف

k شئ را حذف می‌کنیم تا به یک ویژگی دست پیدا کنیم.

مثال: k رأس را حذف کنید تا گراف دوبخشی شود.

زیرگراف القایی غیر مجاز: دور فرد.

ماینورهای گراف:

گرافی که با فشرده‌سازی یال، حذف یال یا حذف رأس به دست بیایند.

مثال: مثلث یک ماینور گراف G است اگر G جنگل نباشد (دور داشته باشد).

درخت جستجوی محدود شده

اگر مجموعه قوانین شاخه شدن (branching rule) برای حل مسأله داشته باشیم که حداقل یکی از آنها به جواب برسد. به شرطی که

هر قانون شاخه شدن حداکثر b(k) شاخه می‌سازد و هر اعمال قانون شاخه شدن پارامتر را کاهش می‌دهد؛ مسأله را می‌توان در زمان O*(b(k)^k) حل کرد.

در بسیاری موارد می‌توان این کران بالا را با تحلیل بهتر بهبود داد.

(دقت کنید که b تابعی از k است.)