زیرمجموعه‌ی $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$. یعنی الگوریتم حریصانه خیلی هم بد عمل نمی‌کند.