گراف ‎$k_{1,3}$‎-آزادِ (یک گراف ‎$k_{1,3}$‎-آزاد است اگر و فقط اگر هیچ زیرگراف القایی ‎$4$‎ رأسی از آن همریخت با ‎$k_{1,3}$‎ نباشد) $n$ رأسیِ ‎$G$‎ داده شده است که ‎$\Delta_G = n-1$‎. می‌خواهیم ‎$r$‎ تا‎ ‎(عدد ‎$r$‎ در ورودی داده می‌شود) از رئوسِ ‎$G$‎ را انتخاب کنیم به‌طوری که زیرگراف القایی حاصل از این ‎$r$‎ رأس بیش‌ترین تعداد یال ممکن را داشته باشد.

فرض کنید در بین تمام ‎$n \choose r$‎ راه ممکن برای این انتخاب، زیر گراف القایی حاصل از زیرمجموعه‌ی ‎$r$‎ عضویِ ‎$S$‎ از رئوس ‎$G$‎، بیش‌ترین تعداد یال ممکن یعنی ‎$T$‎ یال داشته باشد.

الگوریتمی ‎{چندجمله‌ای}‎ بدهید که یک مجموعه‌ی ‎$r$‎-عضوی از رئوس (مانند ‎$S'$‎) بیابد که زیرگراف القایی حاصل از رئوس ‎$S'$‎ حداقل ‎$\lfloor {T\over 2} \rfloor$‎ تا یال داشته باشد.

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