سوال ۱۴

گراف $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$ تا یال داشته باشد.