הקלט ל-Max-Cut-Simple הוא גרף פשוט לא מכוון G=(V,E) ומספר k. השאלה היא האם קיימת U V כך שהחתך (U, U) מכיל לפחו…

הקלט ל-$Max\text{-}Cut\text{-}Simple$ הוא גרף פשוט לא מכוון $G=(V,E)$ ומספר $k$. השאלה היא האם קיימת $U\subseteq V$ כך שהחתך $(U,\bar U)$ מכיל לפחות $k$ קשתות. נוכיח כי $Max\text{-}Cut\text{-}Simple$ ו-$Max\text{-}Cut$ שקולות פולינומית.

1. הראו כי $$Max\text{-}Cut\text{-}Simple\le_p Max\text{-}Cut.$$
2. יהי $G=(V,E)$ מולטיגרף. נסמן ב-$G'$ את הגרף המתקבל מ-$G$ בהוספת שני קודקודים חדשים על כל קשת: לכל קשת $e=uv\in E$ נוסיף $x_e,y_e$ ונחליף את $e$ בקשתות $$ux_e,\quad x_ey_e,\quad y_ev.$$ הוכיחו כי $G'$ פשוט, וכי ב-$G$ קיים חתך בגודל לפחות $k$ אם ורק אם ב-$G'$ קיים חתך בגודל לפחות $$2|E|+k.$$
3. הראו כי $$Max\text{-}Cut\le_p Max\text{-}Cut\text{-}Simple.$$