کاهش تاج (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 رأسی برای پوشش رأسی به دست می‌آید.