מפת הסיבוכיות
EN
חלוקת כל קשת למסלול באורך 3

Max-Cut-Multi ≤p Max-Cut

Max-Cut-Multi≤pMax-Cut\mathrm{Max\text{-}Cut\text{-}Multi}\le_p\mathrm{Max\text{-}Cut} — הקושי של חתך מקסימלי אינו תלוי בקשתות המקבילות; הוא נשאר גם בגרפים פשוטים.

הבנייה

יהי G=(V,E)G=(V,E) מולטיגרף. נגדיר G′=(V′,E′)G'=(V',E'):

  • קודקודים: V′=V∪V′′V'=V\cup V'', כאשר לכל קשת {u,v}∈E\{u,v\}\in E יש ב-V′′V'' שני קודקודים u′,v′u',v' ייחודיים לאותה קשת.
  • קשתות: לכל קשת {u,v}\{u,v\} בגרף המקורי, שלוש הקשתות {u,u′},{u′,v′},{v′,v}.\{u,u'\},\quad\{u',v'\},\quad\{v',v\}.

כלומר כל קשת מוחלפת במסלול באורך 33 דרך שני קודקודים חדשים משלה. הפלט הוא ⟨G′, 2∣E∣+k⟩\langle G',\ 2|E|+k\rangle.

G′G' פשוט. שתי קשתות מקבילות {u,v}\{u,v\} מקבלות ארבעה קודקודי ביניים שונים, ולכן המסלולים שלהן זרים בקודקודי הביניים ואין קשתות מקבילות; לולאה {u,u}\{u,u\} הופכת אף היא למסלול דרך שני קודקודים חדשים ולכן חדלה להיות לולאה.

המחשה

בנייה מודרכת

Max-Cut במולטיגרף → בגרף פשוט

שלב 1 מתוך 7
|E| = 4k = 3
Max-Cut במולטיגרף ברדוקציה ל‑Max-Cut בגרף פשוטמשמאל מולטיגרף עם שתי קשתות מקבילות ולולאה; מימין הגרף הפשוט שבו כל קשת הפכה למסלול באורך שלוש דרך שני קודקודים ייחודיים, עם סימון צדי החתך, הקשתות החוצות ומקרי הזוגיות.G — מולטיגרףe₁e₂e₃e₄abcG′ — גרף פשוטV′ = V ∪ V″ — נבנה בשלב הבא
קודקוד מקורי מ‑V

נכונות — שני הכיוונים

Max-Cut-Multi ∈ ⟹ Max-Cut ∈

נניח שב-GG קיים חתך (U,Uˉ)(U,\bar U) בגודל לפחות kk. נבנה חתך ב-G′G' שיכיל לפחות 2∣E∣+k2|E|+k קשתות.

נתחיל מ-U′⊇UU'\supseteq U (הקודקודים הישנים נשארים בצדם), ונקבע את קודקודי הביניים קשת-קשת. תהי {u,v}∈E\{u,v\}\in E עם קודקודי הביניים u′,v′u',v'.

  • אם הקשת חוצה (u,vu,v בצדדים שונים): נשים את u′u' בצד של vv ואת v′v' בצד של uu. אז שלוש הקשתות {u,u′},{u′,v′},{v′,v}\{u,u'\},\{u',v'\},\{v',v\} כולן חוצות — תרומה 33.
  • אם הקשת אינה חוצה (u,vu,v באותו צד): נשים את u′u' בצד הנגדי ואת v′v' בצד של u,vu,v. אז {u,u′}\{u,u'\} חוצה, {u′,v′}\{u',v'\} חוצה, ו-{v′,v}\{v',v\} אינה — תרומה 22.

לכן כל קשת תורמת לפחות 22, וכל קשת חוצה תורמת 33. אם בחתך המקורי היו c≥kc\ge k קשתות חוצות, סך התרומה הוא 2(∣E∣−c)+3c=2∣E∣+c  ≥  2∣E∣+k.2(|E|-c)+3c=2|E|+c\;\ge\;2|E|+k . לכן ⟨G′,2∣E∣+k⟩∈Max-Cut\langle G',2|E|+k\rangle\in\mathrm{Max\text{-}Cut}.

Max-Cut ∈ ⟹ Max-Cut-Multi ∈

נניח שב-G′G' קיים חתך (W,Wˉ)(W,\bar W) בגודל לפחות 2∣E∣+k2|E|+k. נגדיר U=W∩VU=W\cap V — כלומר מצמצמים את החתך לקודקודים הישנים — ונראה שהחתך המושרה ב-GG מכיל לפחות kk קשתות.

החסם המקומי. תהי {u,v}∈E\{u,v\}\in E עם מסלול הביניים שלה. נבדוק כמה משלוש קשתות המסלול יכולות לחצות, כתלות בצדדים של uu ושל vv בלבד:

  • אם u,vu,v באותו צד ב-WW: המסלול u→u′→v′→vu\to u'\to v'\to v מתחיל ומסתיים באותו צד, ולכן מספר החציות לאורכו הוא זוגי — כלומר 00 או 22. בפרט לכל היותר 22.
  • אם u,vu,v בצדדים שונים: מספר החציות לאורך המסלול הוא אי-זוגי — 11 או 33. בפרט לכל היותר 33.

(הטיעון הוא פשוט מעקב אחרי החלפות צד לאורך מסלול: מספר ההחלפות זוגי אם ורק אם שני הקצוות באותו צד.)

הספירה. נסמן ב-cc את מספר הקשתות של GG ששני קצותיהן בצדדים שונים ב-WW — כלומר בדיוק הקשתות החוצות של (U,Uˉ)(U,\bar U) ב-GG. סך הקשתות החוצות ב-G′G' חסום על ידי 2(∣E∣−c)+3c=2∣E∣+c.2(|E|-c)+3c=2|E|+c . מצד שני הנחנו שהחתך ב-G′G' הוא בגודל לפחות 2∣E∣+k2|E|+k. לכן 2∣E∣+k  ≤  2∣E∣+c⟹c  ≥  k.2|E|+k\;\le\;2|E|+c\quad\Longrightarrow\quad c\;\ge\;k .

כלומר ב-GG קיים חתך בגודל לפחות kk, ומכאן ⟨G,k⟩∈Max-Cut-Multi\langle G,k\rangle\in\mathrm{Max\text{-}Cut\text{-}Multi}.

סיבוכיות הרדוקציה

זמןO(|V| + |E|)
מקוםO(|V| + |E|)
גודל הפלט|V| + 2|E| vertices, 3|E| edges

מעבר יחיד על הקשתות: לכל קשת שני קודקודים חדשים ושלוש קשתות. הסף 2∣E∣+k2|E|+k מחושב בחיבור אחד. הפלט ליניארי בגודל הקלט.

מה זה קונה

יחד עם הרדוקציה הטריוויאלית בכיוון ההפוך (Max-Cut≤pMax-Cut-Multi\mathrm{Max\text{-}Cut}\le_p\mathrm{Max\text{-}Cut\text{-}Multi} — גרף פשוט הוא מולטיגרף), שתי הבעיות שקולות פולינומית. מכאן ש-Max-Cut\mathrm{Max\text{-}Cut} על גרפים פשוטים היא NP-שלמה, למרות שהרדוקציה מ-3NAE\mathrm{3NAE} מייצרת מולטיגרף.

מלכודות

  • קודקודי הביניים חייבים להיות ייחודיים לקשת. אילו שתי קשתות מקבילות חלקו קודקודי ביניים, G′G' לא היה פשוט — וזו כל מטרת הבנייה.

  • הסף אינו kk אלא 2∣E∣+k2|E|+k. כל קשת תורמת "מס" של 22 ללא תלות בכלום, ורק התרומה השלישית נושאת מידע. השכחת המס שוברת את שני הכיוונים.

השרשרת

נשענת על

מאיפה זה נקרא

  • 2026"הוכיחו כי G′G' הוא גרף פשוט, וכי ב-GG קיים חתך בגודל לפחות kk אם ורק אם ב-G′G' קיים חתך בגודל לפחות 2∣E∣+k2|E|+k."
  • 2024אותה בנייה, בניסוח "הוספת שני קודקודים חדשים לכל קשת".
  • 2025אותה בנייה על מולטיגרף עם קשתות מקבילות ולולאות.
  • 2026Max-Cut-Simple\mathrm{Max\text{-}Cut\text{-}Simple} מול הגרסה במולטיגרף.

  • הרדוקציה הזאת אינה מופיעה בשיעורי 2026ב׳ — שיעור 10 עוצר על המולטיגרף ומציין את השאלה כתרגיל כיתה. היא נשאלה בארבעה מועדים לפחות, והבנייה שלמעלה מועתקת מהניסוח שהבחינות עצמן נותנות.