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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(p-1)^d d!

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