1. יהי G=(V,E) גרף שאינו דווקא פשוט - ייתכנו בו קשתות מקבילות ולולאות - ויהי k מספר טבעי. נסמן ב-G' את הגרף הפ…

יהי $G=(V,E)$ גרף שאינו דווקא פשוט - ייתכנו בו קשתות מקבילות ולולאות - ויהי $k$ מספר טבעי. נסמן ב-$G'$ את הגרף הפשוט המתקבל מ-$G$ באמצעות הוספת שני קודקודים חדשים לכל קשת: עבור כל קשת $\{u,v\}$ מוסיפים $w_1,w_2$ ומחליפים אותה בקשתות

הוכיחו כי ב-$G$ קיים חתך בגודל לפחות $k$ אם ורק אם ב-$G'$ קיים חתך בגודל לפחות

נגדיר:

קלט: גרף פשוט לא מכוון $G$ ומספר טבעי $k$.
שאלה: האם קיים ב-$G$ חתך בגודל לפחות $k$?

הוכיחו כי בעיית $Max\text{-}Cut\text{-}Simple$ היא $NP$-קשה.

נגדיר את $Max\text{-}Balanced\text{-}Cut$:

קלט: גרף לא מכוון $G$ ומספר טבעי $k$.
שאלה: האם קיים ב-$G$ חתך $(S,\bar S)$ המקיים $|S|=|\bar S|$ וגודלו לפחות $k$?

הסטודנטית סי והסטודנטית בוכיות הציעו שתי רדוקציות להוכחת $NP$-קושי. לגבי כל אחת קבעו אם היא אכן מוכיחה זאת:

1. הרדוקציה של סי: $$3NAE\le_p Max\text{-}Balanced\text{-}Cut.$$ בהינתן $\varphi$, מחזירים את פלט הרדוקציה מן ההרצאה מ-$3NAE$ ל-$Max\text{-}Cut$.
2. הרדוקציה של בוכיות: $$Max\text{-}Cut\le_p Max\text{-}Balanced\text{-}Cut.$$ בהינתן $G=(V,E)$ ו-$k$, מחזירים את $G'=(V',E)$ המתקבל מהוספת $|V|$ קודקודים מבודדים חדשים, ואת אותו $k$.