הוכחת קירוב חצי ל־Max-Cut

ניתוח חיפוש מקומי בהיפוך קודקוד והוכחת עצירה ויחס חצי.

שאלה

מתחילים מחתך כלשהו ובכל צעד מעבירים קודקוד אם ההעברה מגדילה ממש את מספר הקשתות החוצות. הוכיחו עצירה פולינומית במימוש מתאים והראו שכל אופטימום מקומי הוא לפחות $\mathrm{OPT}/2$ ואף לפחות $|E|/2$.

דרישות קדם

נדרשת שליטה בהגדרות היחידה ובניתוח אורכי קידוד. יש להבחין בין טענה מותנית, רדוקציה ואלגוריתם.

רמז 1

באופטימום מקומי לכל קודקוד לפחות קשתות חוצות מאשר פנימיות.

רמז 2

סכמו על כל הקודקודים.

רמז 3

כל צעד מגדיל פוטנציאל שלם לפחות באחת.

פתרון מלא

נסמן ב-$C$ את הקשתות החוצות וב-$I$ את השאר. עבור קודקוד $v$, יהי $c(v)$ מספר הקשתות החוצות הצמודות לו ו-$i(v)$ מספר הפנימיות. העברת $v$ משנה את ערך החתך ב-$i(v)-c(v)$. לכן באופטימום מקומי $c(v)\ge i(v)$ לכל $v$.

בסכימה על הקודקודים כל קשת נספרת פעמיים:

מכאן $|C|\ge|E|/2$. מאחר ש-$\mathrm{OPT}\le|E|$, נקבל $|C|\ge\mathrm{OPT}/2$.

הערך הוא פוטנציאל שלם בין 0 ל-$|E|$, וכל מהלך משפר אותו לפחות באחת. לכן יש לכל היותר $|E|$ מהלכים. גם מימוש נאיבי הסורק רשימות שכנות אחרי כל צעד הוא פולינומי; שמירת רווח לכל קודקוד משפרת את הזמן.

אסור לאפשר מהלכי רווח אפס ללא כלל שבירת שוויון, כי ייתכן מחזור. בגרף משוקלל הטיעון האיכותי נשמר למשקלים לא־שליליים, אך מספר צעדים החסום בסכום המשקלים עלול להיות פסאודו־פולינומי. הטענה אינה אומרת שאופטימום מקומי הוא גלובלי.

נקודות בדיקה

בדקו שהוכחתם את שני הכיוונים, שכל ענף או מכונה עוצרים, ושגודל הפלט וזמן הבנייה פולינומיים באורך הקלט.

טעויות נפוצות

• ספירת קשתות לא עקבית.
• היפוך כיוון $\mathrm{OPT}\le|E|$.
• מתן צעדים ללא שיפור והבטחת עצירה.

מקורות ואימות

• Merged summary, pp. 61-63
• Papadimitriou, ch. 13
• הערת כיסוי הקורפוס: אין תמליל קירוב מ-2026 המכסה תרגיל זה.
• מיפוי קטלוג: data/exercises.json; הניסוח והפתרון עצמאיים; הגשות אישיות אינן מקור סמכות.

הערת מקור וביטחון

התרגיל הוא סינתזה מקורית. רמת הביטחון משקפת אימות של הטענה המתמטית מול מקורות ספרי הלימוד המפורטים לעיל; מקורות הקורס משמשים רק כאשר זוהה כיסוי ישיר.