الگوریتم تقریبی: پوشش راسی

تقریب مساله ی پوشش راسی بهتر از o(logn) که n تعداد راسها باشد وجود ندارد مگر اینکه P=NP باشد.

مهمترین قدم در به دست آوردن الگوریتم تقریبی به دست آوردن جواب بهینه است که معمولا برای به دست آوردن جواب هم کافی است. در مورد مساله پوشش راسی این اتفاق می افتد.

صورت مساله: یک گراف بدون جهت داریم، کوچکترین زیر مجموعه از راسها را پیدا کنید که حداقل یک سر هر یال در این مجموعه باشد.

فرض کنید الگوریتمی داریم که تعداد راسهای جواب بهینه را می دهد. می توانیم از این تابع برای به دست آوردن جواب بهینه استفاده کنیم.

ایده: حذف یک راس چه تاثیری روی اندازه ی جواب بهینه دارد؟

اگر بعد از حذف آن راس تعداد اعضای جواب تغییر نکرد این راس از اول زیادی بوده است، اما اگر کم شد یعنی جزو جواب است و به زیرمجموعه منتخب اضافه می شود.

وقتی تعداد راسهای منتخب ما صفر شد الگوریتم تمام می شود.

به این ویژگی که بتوان یک مساله را به یک زیرمساله ی مشابه مساله ی اصلی تبدیل کرد خود کاهش پذیری (self reducibility) می گوییم.

معمولا اثبات اینکه یک الگوریتم جوابی می دهد که از a برابر جواب بهینه کمتر است ساده نیست، پس از کران پایین آن استفاده می کنیم. می توانیم برای یک ورودی تابع ویژگی را تعریف کنیم که مقدار آن از هزینه ی جواب بهینه کمتر باشد و ثابت کنیم:

ALG(I) <a*f(I) <a*OPT(I)

برای مساله ی پوشش راسی می توانیم زیرمجموعه ای از یالها را در نظر بگیریم که راس مشترک ندارند. چون هر پوشش راسی باید یک سر این یالها را داشته باشد پس هزینه ی پوشش راسی از تعداد یالهای این مجموعه بیشتر مساوی است. یعنی اندازه ی هر پوشش راسی بیشتر مساوی هر تطابق (matching) است.

چون می خواهیم تقریبی که می زنیم به واقعیت نزدیک باشد، تطابق بیشینه را در نظر می گیریم. یک جواب این است که یک سر همه ی یالهای matching را در نظر بگیریم. چون اگر راس دیگری بتوان به این مجموعه اضافه کرد یعنی matching ما بهینه نبوده است، پس این جواب بهینه است. (برای این حالت)

گفتیم که vertex cover بهینه تعداد راس بیشتری از تعداد یالهای maximum matching دارد و طبق الگوریتم ما راسهای بین یالهای این matching همه قابل پوشش هستند. چون تعداد راسهای matching دو برابر تعداد یالهای آن است پس ضریب تقریب 2 می شود.