$G$، گرافی $n$ رأسی با یال‌های $e_1, e_2, \dots, e_m$ است. می‌خواهیم تعدادی زیرگراف دوبخشی کامل فراگیر از $G$ پیدا کنیم که هر یال $e_i$ حداقل در یکی از این زیرگراف‌ها آمده باشد.

الگوریتمی چندجمله‌ای ارائه دهید که بگوید آیا می‌توان این کار را انجام داد یا نه، و اگر می‌توان حداقل چند زیرگراف لازم است؟