מולטיגרף הוא גרף לא מכוון שעשויות להיות בו קשתות מקבילות ולולאות. הקלט לבעיית Max-Cut-Multi הוא מולטיגרף G=(V,…

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

1. בסעיף זה נוכיח כי

   $$3\text{-}NAE\le_p Max\text{-}Cut\text{-}Multi.$$

   נגדיר את הרדוקציה הבאה.

   קלט: נוסחה $\varphi$ מצורת $3$-$CNF$ מעל המשתנים $x_1,\ldots,x_n$, המכילה $m$ הסגרים.

   1. הרדוקציה תבנה מולטיגרף $G=(V,E)$ באופן הבא:

      • קודקודים: $$V=\{x_1,\ldots,x_n,\bar x_1,\ldots,\bar x_n\}.$$
      • קשתות:
        • קשתות משתנים: בין כל משתנה לשלילתו.
        • קשתות הסגרים: בין כל זוג ליטרלים השייכים לאותו הסגר.

      שימו לב שעשויים להוסיף יותר מקשת אחת בין שני קודקודים. למשל, אם

      $$\varphi=(x_1\vee x_2\vee\bar x_3)\wedge(x_1\vee\bar x_2\vee\bar x_3),$$

      אז בין הקודקודים $x_1$ ו-$\bar x_3$ תוסיף הרדוקציה שתי קשתות. על כן הגרף המתקבל הוא מולטיגרף.

   2. הרדוקציה תחזיר את הגרף $G$ ואת המספר

      $$k=n+2m.$$

   הוכיחו כי האלגוריתם המתואר מהווה רדוקציית זמן פולינומי מ-$3$-$NAE$ ל-$Max\text{-}Cut\text{-}Multi$.

   הערה: ניתן להניח שבנוסחת $3$-$CNF$ מופיעים בכל הסגר בדיוק שלושה ליטרלים משלושה משתנים שונים.

   המלצה: רשמו לעצמכם מספר נוסחאות וראו כיצד האלגוריתם עובד.

2. בסעיף זה נוכיח כי הבעיות $Max\text{-}Cut$ ו-$Max\text{-}Cut\text{-}Multi$ שקולות פולינומית.

   1. הראו כי

      $$Max\text{-}Cut\le_p Max\text{-}Cut\text{-}Multi.$$

   2. יהי $G=(V,E)$ מולטיגרף. נסמן ב-$G'=(V',E')$ את הגרף הבא:

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

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

      $$2|E|+k.$$

   3. הראו כי

      $$Max\text{-}Cut\text{-}Multi\le_p Max\text{-}Cut.$$