زیرمجموعه‌ی ‎$W$‎ از رئوس گراف ‎$G$‎ را یک مجموعه‌ی ‎«$k$-آلوده»‎ می‌گوییم اگر و فقط اگر حداکثر ‎$k$‎ یال از گراف ‎$G$‎ را آلوده کند. یک یال زمانی آلوده می‌شود که حداقل یکی از دو رأس انتهاییش در مجموعه‌ی ‎$W$‎ قرار گیرد. در این مسئله ما می‌خواهیم الگوریتمی برای یافتن مجموعه‌ی‎ $k$-آلوده‌ی ماکسیمم (که تعداد رئوسش بیشینه باشد) پیدا کنیم.

برای این کار الگوریتم حریصانه‌ای پیشنهاد شده است که به این صورت عمل می‌کند:

ابتدا رأس با درجه‌ی مینیمم را انتخاب می‌کند و آن را در مجموعه‌ی ‎$W$‎ قرار می‌دهد. سپس در هر مرحله رئوس ‎$W$‎ و یال‌های متصل به آن‌ها را از گراف ‎$G$‎ حذف می‌کند و رأس با درجه‌ی مینیمم از گراف باقی‌مانده را به ‎$W$‎ اضافه می‌کند. این کار را تا زمانی ادامه می‌دهد که مجموعه‌ی ‎‎‎-$k$ ،‎$W$‎آلوده بماند. بدیهی است اگر با اضافه شدن رأس ‎$v$‎، مجموعه‌ی ‎$W$‎ دیگر ‎$k$-آلوده نبود، الگوریتم ‎$W-v$‎ را به عنوان جواب اعلام می‌کند.

اکنون اگر مجموعه‌ی ‎‎$k$-آلوده‌ی ماکسیمم را با ‎$OPT$‎ و خروجی الگوریتم حریصانه را با ‎$U$‎ نشان دهیم، ثابت کنید ‎$|U| \ge \lfloor \frac{1}{2} \times |OPT| \rfloor$‎. یعنی الگوریتم حریصانه خیلی هم بد عمل نمی‌کند.

• سوال بعد
• سوال قبل