دو مسئله‌ی زیر را درنظر بگیرید:

مسئله‌ی A : گراف $G$ و تعدادی مهره روی بعضی رئوس آن داده شده است. می‌خواهیم مهره‌ها را روی یال‌ها طوری حرکت دهیم که زیرگراف القاییِ رئوسی که شامل حداقل یک مهره‌اند هم‌بند شده و مجموع حرکات مهره‌ها نیز کمینه بشود.

مسئله‌ی B : گراف دوبخشی $H$ که مجموعه‌ی رئوس دو بخش آن $X$ و $Y$ می‌باشند داده شده است. می‌خواهیم کوچک‌ترین زیرمجموعه‌ی $X$ مانند $S$ را پیدا کنیم به طوری که $N(S)=Y$.

ثابت کنید اگر برای مسئله‌ی $A$ الگوریتم چندجمله‌ای وجود داشته باشد برای مسئله‌ی $B$ نیز الگوریتم چندجمله‌ای وجود دارد.