13Approximation Algorithms I: A 2-Approximation for Vertex Cover, a ½-Approximation for Max-Cut, and the Inapproximability of TSP

בקצרה

• לפני הכול, שלוש גרסאות של אותה בעיה: הכרעה (שאלת כן/לא — שפה), חיפוש (מצא עד או דווח שאין) ואופטימיזציה (מצא את הערך/הפתרון הטוב ביותר — פונקציה, לא שפה). NP-קושי מוגדר פורמלית רק לגרסת ההכרעה, ולכן טענות אי-קירוב מנוסחות כתוצאות מותנות.
• זהו השיעור הראשון שבו אנחנו מוותרים על אופטימליות במקום לוותר על זמן ריצה פולינומי. אלגוריתם קירוב חייב תמיד להחזיר פתרון אפשרי (feasible), רץ בזמן פולינומי, ומבטיח שהערך שלו רחוק מהאופטימום לכל היותר בפקטור $\alpha$.
• הטכניקה המרכזית של כל השיעור: האלגוריתם אינו יודע לחשב את $\mathrm{OPT}$ — הרי זו בדיוק הבעיה הקשה. לכן מוצאים גודל עזר שהאלגוריתם כן שולט בו, מוכיחים שהוא חוסם את $\mathrm{OPT}$ (מלמטה בבעיית מינימום, מלמעלה בבעיית מקסימום), ומשווים אליו את הפלט.
• 2-קירוב ל-$\mathrm{VC}$: בחר קשת, הכנס את שני קצותיה לכיסוי, מחק את שניהם, חזור. גודל העזר הוא הזיווג $F$ של הקשתות שנבחרו: $|F| \le |C_{\mathrm{opt}}|$ ו-$|C| = 2|F|$, ולכן $|C| \le 2|C_{\mathrm{opt}}|$.
• להוסיף קצה אחד במקום שניים נשמע חסכוני יותר — ואינו נותן קירוב ביחס קבוע כלל. הדוגמה הנגדית היא כוכב.
• הניתוח הדוק ביחס לאלגוריתם: על גרף שהוא זיווג מושלם האלגוריתם מחזיר את כל הקודקודים בעוד שהאופטימום הוא חצי מהם. שאלה אחרת לגמרי, ופתוחה עד היום, היא האם לבעיה יש אלגוריתם קירוב טוב מ-$2$.
• ½-קירוב ל-$\mathrm{MAXCUT}$ בחיפוש מקומי: כל עוד יש קודקוד שהעברתו לצד השני מגדילה את החתך — העבר אותו. בסיום מתקיים $\mathrm{cut}(v)\ge \mathrm{other}(v)$ לכל $v$, וספירה כפולה נותנת $|F| \ge \tfrac12|E| \ge \tfrac12 K$.
• תוצאת קושי מותנית: לכל $\alpha \ge 1$, אלגוריתם קירוב ביחס $\alpha$ לבעיית הסוכן הנוסע הכללית גורר $\mathrm{P}=\mathrm{NP}$ — ולמעשה שקול לכך. זו הדגמה של איך הופכים אלגוריתם קירוב לאלגוריתם הכרעה.
• שני הכלים החדשים למבחן: הוכחת פיזביליות בנפרד מהוכחת היחס, וחסימת $\mathrm{OPT}$ באמצעות גודל עזר.

רקע ותלויות

מ־שיעור 12 (הסוף שלו) — בעיית אופטימיזציה ואלגוריתם קירוב. הסיכום של שיעור 13 נפתח ישירות באלגוריתם, כי ההגדרות ניתנו בדקות האחרונות של המפגש הקודם ונרשמו בעמוד 6 של סיכום שיעור 12. העמוד ההוא שייך מבחינת התוכן לשיעור הזה, ולכן הוא מטופל כאן במלואו — הטבלה המשולשת שבו בהגדרה 1, ההגדרה הפורמלית של בעיית אופטימיזציה בהגדרה 2, והגדרת אלגוריתם הקירוב בהגדרה 3. להלן תמצית קצרה של מה שנדרש כדי לקרוא את המשפטים; הניסוחים המלאים והדוגמאות נמצאים בפרק ההגדרות.

בעיית אופטימיזציה מורכבת מ־(א) קבוצת קלטים אפשריים $\mathcal{I}$ — למשל, עבור כיסוי בקודקודים, אוסף כל הגרפים הלא מכוונים; (ב) לכל קלט $I \in \mathcal{I}$, קבוצת פתרונות אפשריים $X_I$ — עבור $\mathrm{VC}$, כל הכיסויים בקודקודים של $G$; (ג) פונקציית ערך $v: X_I \to \mathbb{R}$ — עבור $\mathrm{VC}$, גודל הקבוצה. המטרה: למצוא $x \in X_I$ שעבורו $v(x)$ מינימלי (או מקסימלי, תלוי בבעיה).

הערה על שני צירים [02:01:23 בתמלול 18]: יש כאן שני צירים שאפשר "להתפשר" עליהם — האם הפתרון אפשרי, ומה ערכו. בקורס הזה מתפשרים רק על הערך. אלגוריתם קירוב ל-$\mathrm{VC}$ שמקבל גרף חייב להחזיר כיסוי בקודקודים; לא כיסוי "כמעט". יש תחום מחקר שלם שמתפשר גם על זה, ואיננו עוסקים בו.

הגדרת אלגוריתם הקירוב לבעיית מינימיזציה (מילה במילה כפי שניתנה): עבור $\alpha \ge 1$, אלגוריתם קירוב לבעיית מינימיזציה עם יחס קירוב $\alpha$ הוא אלגוריתם שעבור כל קלט $I$ לבעיה — (1) רץ בזמן פולינומי ב-$|I|$; (2) מחזיר פתרון אפשרי $x \in X_I$; (3) מקיים $\mathrm{OPT}(I) \;\le\; v(x) \;\le\; \alpha \cdot \mathrm{OPT}(I),$ כאשר $\mathrm{OPT}(I) = \min_{y \in X_I} v(y)$. אי-השוויון השמאלי טריוויאלי — פתרון אפשרי לא יכול להיות זול מהמינימום מבין הפתרונות האפשריים; כל העבודה היא באי-השוויון הימני.

הבעיה שהמרצה השאיר כ־cliffhanger בסוף שיעור 12 [02:07:08]: אם האלגוריתם אינו יודע לחשב את $\mathrm{OPT}$ — הרי חישובו הוא בדיוק הבעיה הקשה — איך בכלל הוא יכול לדעת שמה שהחזיר אינו גדול מפי $2$ מ-$\mathrm{OPT}$? התשובה ניתנת בשיעור הזה, והיא ליבת משפט 1.

מ־שיעור 10 — הבעיות עצמן. $U \subseteq V$ היא כיסוי בקודקודים של $G=(V,E)$ אם לכל קשת $xy \in E$ מתקיים $x \in U$ או $y \in U$. גרסת האופטימיזציה: בהינתן $G$, מצא כיסוי בקודקודים בגודל מינימלי. בעיית $\mathrm{MAXCUT}$: בהינתן $G$, חלק את $V$ לשתי קבוצות כך שמספר הקשתות ה"חוצות" יהיה מקסימלי. שתיהן NP-קשות בגרסת ההכרעה שלהן.

מ־שיעור 12 — מעגל המילטוני ובעיית הסוכן הנוסע. $\mathrm{UHC}$ (Undirected Hamiltonian Cycle) — האם קיים בגרף לא מכוון מעגל העובר בכל קודקוד בדיוק פעם אחת — היא NP-שלמה. בשיעור 12 נראתה גם הרדוקציה $\mathrm{UHC} \le_p \mathrm{TSP}$, שבה נתנו לקשתות המקוריות משקל $1$ ולשאר משקל $2$. נזכיר את כיוון הסימון: $A \le_p B$ פירושו ש-$A$ ניתנת לרדוקציה ל-$B$, כלומר $B$ קשה לפחות כמו $A$.

מאלגוריתמים / מתמטיקה בדידה — שני כלים שנשתמש בהם במפורש:

1. משפט הדרגות (lemma of handshakes): בכל גרף $G=(V,E)$ מתקיים $\sum_{v \in V} \deg_G(v) = 2|E|$, כי כל קשת תורמת $1$ לדרגת כל אחד משני קצותיה.
2. עקרון שובך היונים בניסוח של פונקציות [00:26:19]: אם קיימת פונקציה חד-חד-ערכית $f: A \to B$ אז $|A| \le |B|$. בקונטרפוזיציה: אם ב-$A$ יש יותר איברים מאשר ב-$B$, אז אף פונקציה מ-$A$ ל-$B$ אינה חד-חד-ערכית — זהו בדיוק שובך היונים.

הגדרות

הגדרה 1: שלוש הגרסאות של בעיה — הכרעה, חיפוש ואופטימיזציה

לבעיות רבות יש שלוש גרסאות שונות, ואת ההבחנה ביניהן צריך לעשות לפני שמדברים על קירוב בכלל. הטבלה הבאה היא הטבלה שבעמוד 6 של סיכום שיעור 12, בדוגמה של $\mathrm{VC}$:

הבחנה טכנית שהמרצה הדגיש [01:52:35]–[01:53:07]. רק לבעיית ההכרעה יש "שאלה"; לשתי האחרות יש "מטרה". ההבדל אינו סמנטי בלבד: בעיית הכרעה היא שפה (קבוצה), כי היא שאלת כן/לא, ולכן אפשר לדבר עליה במונחים של $\mathrm{P}$, $\mathrm{NP}$ ורדוקציות. בעיית אופטימיזציה אינה שפה אלא פונקציה — מקבלים גרף וצריך להחזיר מספר (או פתרון). זו הסיבה שאמרנו בשיעור 12 [01:55:13] ש-NP-קושי מוגדר פורמלית לבעיות הכרעה בלבד, כי הוא מוגדר באמצעות רדוקציות בין שפות; ובכל זאת גרסת האופטימיזציה של בעיה NP-קשה היא "קשה" במובן המעשי, ולכן משפט 4 בקובץ הזה מנוסח כתוצאת קושי מותנית ולא כטענת NP-קושי.

שתי תת-גרסאות של האופטימיזציה [01:51:32], [01:52:05]. אפשר לדרוש רק את הערך האופטימלי (הגודל המינימלי של כיסוי), ואפשר לדרוש את הפתרון עצמו (כיסוי בגודל מינימלי). שתיהן נקראות "בעיית אופטימיזציה", וההבדל דומה להבדל בין "מהו משקל המסלול הקל ביותר" לבין "מהו המסלול הקל ביותר". הדרישה חייבת להיות חלק מהגדרת הבעיה — זו בדיוק הנקודה שבה נפתחה ההקלטה של שיעור 13 [00:00:00]. בקורס הזה מתמקדים בגודל.

הקשר בין הגרסאות. הסדר הוא מהקל לכבד:

1. בעיית החיפוש היא הקשחה של בעיית ההכרעה [01:50:54]: לא מספיק לומר "כן", צריך גם להציג עד.
2. פותר יעיל לגרסת האופטימיזציה נותן פותר יעיל לגרסת ההכרעה [01:54:42]. ההוכחה, שהמרצה נתן במפורש: בהינתן $\langle G,k \rangle$, הרץ את פותר האופטימיזציה על $G$, קבל את הגודל המינימלי $m$, והחזר "כן" אם ורק אם $m \le k$. זו קריאה אחת ובדיקה אחת, ולכן פולינומית. במילותיו: "אם אני יודע לפתור את זה, אני יודע לפתור את זה."
3. מכאן נובעת המסקנה שמעניינת אותנו: אם את גרסת ההכרעה איננו יודעים לפתור ביעילות, אז בוודאי לא את גרסת האופטימיזציה. זו הסיבה שבשיעור הזה מוותרים על אופטימליות.

הערה על הכיוון ההפוך. המרצה לא טען בשיעור את הכיוון ההפוך (בנייה של פותר אופטימיזציה מפותר הכרעה, למשל בחיפוש בינארי על $k$ ואז self-reducibility), ולכן הוא אינו נטען כאן כתוצאה של השיעור. הוא כן משתמש בגרסה חלשה שלו במסקנת השקילות של משפט 4 [01:25:28], שם די בכך שאם $\mathrm{P}=\mathrm{NP}$ אפשר לפתור במדויק.

אינטואיציה כללית — למה בכלל התחלנו בזה [01:43:50]–[01:47:27]. זהו הפרק השלישי בקורס, "התמודדות עם NP-קושי". עד היום כל האלגוריתמים שראיתם (דייקסטרה, קרוסקל) החזירו תשובה מדויקת. כאן, לראשונה, מוותרים על משהו כדי לקבל זמן ריצה פולינומי: אלגוריתמי קירוב מוותרים על אופטימליות, ואלגוריתמים אקראיים (השיעורים הבאים) מוותרים על ודאות. בשני המקרים מתעקשים על גרנטי כמותי — "טועה, אבל לא יותר מדי" / "לא אופטימלי, אבל לא רחוק מדי". והמרצה הוסיף אזהרה: זה לא אומר שהבעיה באמת קשה; ייתכן ש-$\mathrm{VC}$ בכלל ב-$\mathrm{P}$ — פשוט איננו יודעים לפתור אותה [01:45:24].

אי-מופע: "האם קיים כיסוי בקודקודים בגודל $k$" אינה בעיית אופטימיזציה, גם אם $k$ קטן מאוד — אין בה פונקציית ערך למזער; היא שפה.

הגדרה 2: בעיית אופטימיזציה (הגדרה פורמלית)

בעיית אופטימיזציה מורכבת מארבעה רכיבים (עמוד 6 בסיכום שיעור 12; [01:57:00]–[02:00:51] בתמלול 18):

1. קבוצה $\mathcal{I}$ של קלטים אפשריים;
2. לכל קלט $I \in \mathcal{I}$, אוסף $X_I$ של פתרונות אפשריים (feasible);
3. פונקציית ערך $v : X_I \to \mathbb{R}$;
4. המטרה: מבין הפתרונות האפשריים, למצוא פתרון אפשרי $x \in X_I$ שעבורו $v(x)$ אופטימלי — מינימלי או מקסימלי, לפי הבעיה.

המופע של $\mathrm{VC}$ (העמודה הכחולה בעמוד 6):

1. $\mathcal{I}$ היא אוסף כל הגרפים הלא מכוונים;
2. לכל גרף $G=(V,E)$, כל כיסוי בקודקודים ב-$G$ נקרא פתרון אפשרי;
3. הערך של פתרון אפשרי הוא גודלו;
4. מבין כל הכיסויים בקודקודים מחפשים מינימלי.

אינטואיציה — שני צירים, מתפשרים רק על אחד [02:01:23]. הרכיב (2) והרכיב (3) הם שני צירים נפרדים: האם הפתרון אפשרי, ומה ערכו. אלגוריתם קירוב ל-$\mathrm{VC}$ חייב להחזיר כיסוי; על הערך הוא רשאי להתפשר. יש קו מחקר שלם שמתפשר גם על הפיזביליות — לא בקורס הזה.

אי-מופע: למה דווקא מינימום ב-$\mathrm{VC}$ ולא מקסימום [02:02:24]? כי כיסוי מקסימלי הוא טריוויאלי — כל קבוצת הקודקודים היא תמיד כיסוי. באופן סימטרי, ב-$\mathrm{CLIQUE}$ ו-Independent Set מחפשים מקסימום כי כל קודקוד בודד הוא קליק, וב-$\mathrm{MAXCUT}$ מחפשים מקסימום כי $U=\emptyset$ נותן תמיד חתך בגודל $0$. "יש היגיון בטירוף": מגדירים תמיד את הכיוון המעניין, כי בכיוון השני התשובה ידועה מראש.

הגדרה 3: אלגוריתם קירוב ביחס $\alpha$

(א) בעיית מינימיזציה (הניסוח שבעמוד 6 בסיכום שיעור 12, [02:05:02] בתמלול 18). עבור $\alpha \ge 1$, אלגוריתם קירוב לבעיית מינימיזציה עם יחס קירוב $\alpha$ הוא אלגוריתם שעבור כל קלט $I$ לבעיה: רץ בזמן פולינומי ב-$|I|$, מחזיר פתרון אפשרי $x \in X_I$, ומקיים $\mathrm{OPT}(I) \;\le\; v(x) \;\le\; \alpha \cdot \mathrm{OPT}(I), \qquad \mathrm{OPT}(I) = \min_{y \in X_I} v(y).$

(ב) בעיית מקסימיזציה (לא בעמוד 6; נאמר בעל פה בשיעור הזה [00:36:24]). עבור $0 < \alpha \le 1$, אלגוריתם קירוב לבעיית מקסימיזציה עם יחס קירוב $\alpha$ הוא אלגוריתם שעבור כל קלט $I$: רץ בזמן פולינומי ב-$|I|$, מחזיר פתרון אפשרי $x \in X_I$, ומקיים $\alpha \cdot \mathrm{OPT}(I) \;\le\; v(x) \;\le\; \mathrm{OPT}(I), \qquad \mathrm{OPT}(I) = \max_{y \in X_I} v(y).$

אינטואיציה. בשני המקרים שלושה דברים צריך לוודא [02:06:37]: זמן פולינומי, פיזביליות, וחסם על הערך. אחד משני אי-השוויונות הוא תמיד טריוויאלי — במינימיזציה זה $\mathrm{OPT} \le v(x)$ (פתרון אפשרי לא יכול להיות זול מהמינימום), ובמקסימיזציה זה $v(x) \le \mathrm{OPT}$ (אי אפשר להחזיר פתרון טוב מהמקסימלי). כל העבודה היא באי-השוויון השני.

מופע: אלגוריתם שמחזיר חתך בגודל לפחות חצי מהחתך המקסימלי הוא אלגוריתם קירוב ביחס $\tfrac12$ (משפט 3); האלגוריתם של משפט 1 הוא אלגוריתם קירוב ביחס $2$.

אי-מופע חשוב [00:36:24]: אלגוריתם ל-Independent Set שמחזיר תמיד קודקוד בודד הוא אמנם פולינומי ואמנם מחזיר פתרון אפשרי — אבל אין שום $\alpha>0$ קבוע שעבורו הוא אלגוריתם קירוב ביחס $\alpha$, כי $\mathrm{OPT}$ יכול לגדול עם הגרף בעוד הפלט נשאר $1$. פתרון אפשרי כשלעצמו אינו מספיק; היחס חייב להיות קבוע שאינו תלוי בקלט.

שימו לב לקונבנציה של הקורס. כאן $\alpha \ge 1$ לבעיות מינימום ו-$\alpha \le 1$ לבעיות מקסימום — כלומר $\alpha$ הוא תמיד היחס $\mathrm{ALG}/\mathrm{OPT}$ בכיוון שבו הוא נמדד. הסיכום כותב בהתאם "אלגוריתם קירוב פי $2$" ל-$\mathrm{VC}$ ו"אלגוריתם קירוב פי $\tfrac12$" ל-$\mathrm{MAXCUT}$. ספרים אחרים מנרמלים גם בעיות מקסימום ל-$\alpha \ge 1$ וכותבים $\mathrm{OPT}/\mathrm{ALG} \le \alpha$; בקובץ הזה נשמרת הקונבנציה של הקורס.

הקושי שהמרצה השאיר כשאלה פתוחה בסוף שיעור 12 [02:07:08]: האלגוריתם אינו יודע את $\mathrm{OPT}(I)$ — חישובו הוא בדיוק הבעיה הקשה. אז איך הוא בכלל יכול להתחייב ש-$v(x) \le \alpha \cdot \mathrm{OPT}(I)$? "זה הקסם, אבל זה כמו הקסם של רדוקציה." התשובה נמצאת במשפט 1: גודל עזר שחוסם את $\mathrm{OPT}$.

הגדרה 4: זיווג (קשתות זרות בזוגות)

קבוצת קשתות $F \subseteq E$ נקראת זרה בזוגות (זיווג, matching) אם לכל $e, \hat e \in F$ עם $e \ne \hat e$ מתקיים $e \cap \hat e = \emptyset$, כלומר אין להן קודקוד משותף.

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

מופע: בגרף המעגל $C_6$ עם קודקודים $1,\dots,6$, הקבוצה $\{12, 34, 56\}$ היא זיווג. אי-מופע: $\{12, 23\}$ אינה זיווג, כי $12 \cap 23 = \{2\}$.

הגדרה 5: החתך המושרה, ו-$\mathrm{cut}(v)$ מול $\mathrm{other}(v)$

יהי $G=(V,E)$ ותהי $U \subseteq V$, ונסמן $\bar U = V \setminus U$. החתך המושרה על ידי $U$ הוא קבוצת הקשתות $F \;=\; \{\, xy \in E \;\mid\; |\{x,y\} \cap U| = 1 \,\},$ כלומר כל הקשתות שיש להן בדיוק קצה אחד ב-$U$. לכל $v \in V$ נסמן:

• $\mathrm{cut}(v)$ — מספר הקשתות הסמוכות ל-$v$ ששייכות לחתך (הקצה השני שלהן בצד הנגדי);
• $\mathrm{other}(v)$ — מספר הקשתות הסמוכות ל-$v$ שאינן בחתך (הקצה השני שלהן באותו צד).

קשת נקראת סמוכה ל-$v$ אם $v$ הוא אחד מקצותיה.

אינטואיציה. כל קשת הנוגעת ב-$v$ היא או "חוצה" או "פנימית", ולכן באופן מיידי $\mathrm{cut}(v) + \mathrm{other}(v) \;=\; \deg_G(v) \qquad \text{for all } v \in V .$

מופע: בגרף המשולש $\{a,b,c\}$ עם $U=\{a\}$: החתך הוא $\{ab, ac\}$, ומתקיים $\mathrm{cut}(a)=2, \mathrm{other}(a)=0$; $\mathrm{cut}(b)=1, \mathrm{other}(b)=1$ (הקשת $bc$ פנימית). אי-מופע: עבור $U=\emptyset$ החתך ריק ו-$\mathrm{cut}(v)=0$ לכל $v$ — קבוצה ריקה היא פתרון אפשרי לגמרי, פשוט גרוע.

הגדרה 6: גרסת האופטימיזציה של בעיית הסוכן הנוסע

קלט: גרף שלם $\hat G=(V,\hat E)$ ופונקציית משקלים $w:\hat E \to \mathbb{Q}_{\ge 0}$. פתרונות אפשריים: כל המעגלים ההמילטוניים ב-$\hat G$ (מעגל שעובר בכל קודקוד בדיוק פעם אחת). שימו לב שבגרף שלם תמיד קיים כזה. ערך: $w(C)=\sum_{e \in C} w(e)$. מטרה: מינימיזציה.

אינטואיציה [01:21:14]. נקודת בלבול נפוצה מהכיתה: המשקל שמעניין אותנו הוא של המעגל, לא של הגרף. במעגל המילטוני יש בדיוק $|V|$ קשתות, לא משנה כמה קשתות יש בגרף השלם עצמו.

מופע: על $K_4$ עם משקל $1$ לקשתות $12,23,34,41$ ומשקל $9$ לאלכסונים, המעגל $1\!-\!2\!-\!3\!-\!4\!-\!1$ הוא פתרון אפשרי בערך $4$, וזהו האופטימום.

משפטים והוכחות

משפט 1: קיים אלגוריתם קירוב ביחס $2$ לבעיית הכיסוי בקודקודים

האלגוריתם (עמוד 1 בסיכום). על קלט $G=(V,E)$:

1. אתחל $C \leftarrow \emptyset$, וכן $F \leftarrow \emptyset$.
2. כל עוד יש בגרף קשת $e = xy$:
   1. הוסף את $x$ ואת $y$ ל-$C$; הוסף את $e$ ל-$F$.
   2. מחק מהגרף את $x$ ואת $y$ ואת כל הקשתות המחוברות ל-$x$ או ל-$y$.
3. החזר את $C$.

הערה [00:03:12]–[00:03:43]: בגרסה הראשונה שנכתבה על הלוח שלב 2.2 היה "מחק את הקשת $e$ ואת כל הקשתות המחוברות ל-$x$ ול-$y$". סטודנט העיר שמחיקת הקשת $e$ מיותרת — ברגע שמוחקים את הקודקודים $x,y$, כל הקשתות הנוגעות בהם, ובכללן $e$ עצמה, נעלמות. המרצה קיבל את התיקון ("אתה צודק ב-100%"), וזו הגרסה שנרשמה. הקובץ הזה משתמש בגרסה המתוקנת.

הערה: השורה $F \leftarrow \emptyset$ ותוספת $e$ ל-$F$ אינן חלק אמיתי מהאלגוריתם [00:30:04]. האלגוריתם אינו צריך את $F$ כדי לרוץ, והיא לא משפיעה על הפלט. היא קיימת אך ורק לצורך הניתוח, ולכן נכתבה בסיכום בצבע אחר. זהו דפוס שחוזר בכל השיעור: מוסיפים לאלגוריתם "משתנה רפאים" שנותן לנו נקודת ייחוס להשוואה מול האופטימום.

טענה א (זמן ריצה). האלגוריתם רץ בזמן $O(|E|^2)$, ובפרט בזמן פולינומי בגודל הקלט.

הוכחה. נבחן מה "מתקדם" בכל איטרציה. בכל איטרציה של הלולאה נבחרת קשת $e$ ונמחקים שני קצותיה, ולכן נמחקת לפחות קשת אחת (הקשת $e$ עצמה). מספר הקשתות אינו גדל אף פעם, ולכן מספר האיטרציות קטן או שווה ל-$|E|$. בכל איטרציה, מציאת קשת ומחיקת הקודקודים והקשתות הסמוכות עולה לכל היותר מעבר על כל הגרף, כלומר $O(|V|+|E|)$, ובחסם גס לכל היותר $|E|$ מחיקות. סך הכל $O(|E|^2)$ — פולינומי בגודל הקלט. $\blacksquare$

הערה מתודית [00:06:53]–[00:10:53]: סטודנט נתן ניתוח הדוק בהרבה — כל קשת "נוגעים" בה לכל היותר פעם אחת (או שעוברים עליה ואז מוחקים אותה, או שהיא נמחקת כתוצאה ממחיקת שכן), ולכן זמן הריצה הוא $O(|E|)$. המרצה אישר שהניתוח נכון ומעולה, אך העדיף בכוונה את הניתוח הגס: "כל מה שמעניין אותי זה שזה פולינומי; אם אני לא חייב, אני לא עושה עבודות יזומות". במבחן — החסם הגס מספיק, ובלבד שהוא נכון.

טענה ב (פיזביליות). יהי $G=(V,E)$ ותהי $C$ הקבוצה המוחזרת על ידי האלגוריתם. אז $C$ היא כיסוי בקודקודים של $G$.

הוכחה. ראשית נבחין באינוריאנטה: קודקוד נמחק מהגרף אם ורק אם הוא הוכנס ל-$C$. אכן, המחיקה היחידה מתבצעת בשלב 2.2 ומתייחסת בדיוק לשני הקודקודים שהוכנסו ל-$C$ בשלב 2.1.

תהי $e = xy \in E$ קשת שרירותית של הגרף המקורי. האלגוריתם עוצר רק כשאין קשתות בגרף, ולכן בסיום הריצה $e$ אינה בגרף — כלומר $e$ נמחקה במהלך הריצה (אחרת האלגוריתם לא היה עוצר). קשת נמחקת רק בשלב 2.2, וזה קורה באחד משלושה מקרים:

• מקרה 1: $e$ הייתה הקשת שהאלגוריתם בחר באיטרציה. אז לפי שלב 2.1 מתקיים $x \in C$ וגם $y \in C$, ובפרט $x \in C$ או $y \in C$.
• מקרה 2: $e$ נמחקה כתוצאה ממחיקת $x$ (כלומר $x$ היה קצה של קשת אחרת שנבחרה). לפי האינוריאנטה $x \in C$, ולכן $x \in C$ או $y \in C$.
• מקרה 3: $e$ נמחקה כתוצאה ממחיקת $y$. באופן סימטרי $y \in C$, ולכן $x \in C$ או $y \in C$.

בכל המקרים לפחות אחד מקצות $e$ שייך ל-$C$. מכיוון ש-$e$ הייתה שרירותית, $C$ מכסה את כל קשתות $G$. $\blacksquare$

הערה: מקרה 1 הוא למעשה מקרה פרטי של מקרים 2–3 בגרסה המתוקנת של האלגוריתם (הקשת הנבחרת נמחקת בדיוק בגלל מחיקת קצותיה). הסיכום מונה את שלושתם בנפרד, וכך גם נשמר כאן, כי בגרסה שעל הלוח בתחילת השיעור המחיקה של $e$ הייתה מפורשת ולכן המקרה היה נפרד באמת.

שימו לב לניסוח [00:14:01]: גם כשמקבלים "$x \in C$ וגם $y \in C$", המרצה התעקש לסיים את המשפט ב"ובפרט $x\in C$ או $y\in C$" — כי זה בדיוק מה שההגדרה של כיסוי דורשת. "זה הקורד שאני חייב לסיים איתו את הדבר הזה."

טענה ג (יחס הקירוב). יהי $C_{\mathrm{opt}}$ פתרון אופטימלי (כיסוי בקודקודים בגודל מינימלי) עבור $G$. אז $|C_{\mathrm{opt}}| \;\le\; |C| \;\le\; 2\,|C_{\mathrm{opt}}| .$

הוכחה. אי-השוויון השמאלי מיידי: לפי טענה ב, $C$ הוא כיסוי בקודקודים, ואין כיסוי בקודקודים קטן מהמינימלי.

לאי-השוויון הימני נשתמש ב-$F$. תהי $e \in F$ קשת כלשהי שהאלגוריתם בחר. מכיוון ש-$C_{\mathrm{opt}}$ הוא כיסוי בקודקודים של $G$, ומכיוון ש-$e \in E$, חייב להיות לפחות אחד מקצותיה של $e$ ב-$C_{\mathrm{opt}}$. נגדיר פונקציה $\varphi: F \to C_{\mathrm{opt}}, \qquad \varphi(e) = \text{one endpoint of } e \text{ that lies in } C_{\mathrm{opt}}$ (אם שני הקצוות ב-$C_{\mathrm{opt}}$ נבחר אחד מהם באופן שרירותי — לא משנה איזה). הפונקציה מוגדרת היטב בדיוק בזכות היות $C_{\mathrm{opt}}$ כיסוי.

$\varphi$ חד-חד-ערכית. יהיו $e, \hat e \in F$ עם $e \ne \hat e$. לפי מבנה האלגוריתם, ברגע שקשת נכנסת ל-$F$ שני קצותיה נמחקים מהגרף יחד עם כל הקשתות הנוגעות בהם; לכן שום קשת שתיבחר אחר כך לא תיגע בהם. נובע ש-$e \cap \hat e = \emptyset$, כלומר $F$ היא קבוצת קשתות זרות בזוגות (זיווג). ומכיוון ש-$\varphi(e)$ הוא קצה של $e$ ו-$\varphi(\hat e)$ הוא קצה של $\hat e$, ושתי הקשתות זרות, בהכרח $\varphi(e) \ne \varphi(\hat e)$.

לפי עקרון שובך היונים בניסוח של פונקציות, קיום פונקציה חד-חד-ערכית מ-$F$ ל-$C_{\mathrm{opt}}$ נותן $|F| \;\le\; |C_{\mathrm{opt}}| .$

מצד שני, בכל איטרציה הכנסנו קשת אחת ל-$F$ ושני קודקודים חדשים ל-$C$ (חדשים, כי אחרי המחיקה הם לא יופיעו שוב), ולכן $|C| \;=\; 2\,|F| .$

בשילוב: $|C| = 2|F| \le 2|C_{\mathrm{opt}}|$. $\blacksquare$

הערה: זו ליבת השיעור [00:18:45]. האלגוריתם אינו יודע לחשב את $|C_{\mathrm{opt}}|$, ואפילו לא לדבר עליו. הפתרון הוא לקחת גודל אחר, $|F|$, שנוח לעבוד איתו, להראות שהוא חוסם מלמטה את האופטימום, ולהראות שהפלט אינו גדול מפי $2$ ממנו. זהו התבנית הכללית לכל בעיית מינימיזציה: מצא חסם תחתון על $\mathrm{OPT}$ שהאלגוריתם שולט בו.

הערה: כאן מתברר למה מוחקים את שני הקודקודים [00:24:10]. אילו היינו מוחקים רק קודקוד אחד, שתי קשתות ב-$F$ היו יכולות לחלוק קודקוד, $\varphi$ לא הייתה בהכרח חד-חד-ערכית, וכל ההוכחה קורסת. ראו תרגיל 3 בהמשך לדוגמה נגדית מפורשת.

משפט 2: הניתוח של משפט 1 הדוק ביחס לאלגוריתם

ניסוח. קיימת משפחה אינסופית של גרפים שעליהם האלגוריתם של משפט 1 מחזיר כיסוי בגודל בדיוק $2|C_{\mathrm{opt}}|$. לכן לא ניתן לשפר את הקבוע $2$ בטענה ג עבור האלגוריתם הזה.

הוכחה. לכל $n \ge 1$ נגדיר את $M_n$: גרף על $2n$ קודקודים $x_1,y_1,\dots,x_n,y_n$ שקשתותיו הן $x_iy_i$ לכל $i$ — כלומר $n$ קשתות זרות בזוגות (זיווג מושלם, ולא גרף רדוקיבילי במובן כלשהו; המרצה הדגיש שזה בדיוק "זיווג" [00:34:16]).

התנהגות האלגוריתם: בכל איטרציה נבחרת אחת מהקשתות $x_iy_i$; שני קצותיה נכנסים ל-$C$ ונמחקים; אף קשת אחרת אינה נוגעת בהם, ולכן כל שאר הקשתות נשארות. לאחר $n$ איטרציות $C = \{x_1,y_1,\dots,x_n,y_n\}$, כלומר $|C| = 2n = |V|$ — כל הגרף.

האופטימום: הקשתות זרות בזוגות, ולכן כל כיסוי חייב להכיל לפחות קודקוד אחד מכל קשת, ומכאן $|C_{\mathrm{opt}}| \ge n$. מצד שני, בחירת קצה אחד מכל קשת נותנת כיסוי בגודל $n$. לכן $|C_{\mathrm{opt}}| = n$, ומספר הפתרונות האופטימליים הוא $2^{n} = 2^{|V|/2}$ (שתי בחירות לכל קשת) [00:35:19].

מכאן $|C| = 2n = 2|C_{\mathrm{opt}}|$. $\blacksquare$

למה צריך משפחה אינסופית ולא גרף בודד [00:34:16]: אם מציגים דוגמה נגדית קטנה אחת, אפשר לטעון "על גרף כזה אני פשוט פותר ידנית". כדי לומר משהו על האלגוריתם צריך אינסטנס גדול כרצוננו — לכן $M_n$ לכל $n$.

שתי שאלות שונות לחלוטין [00:31:09]–[00:33:12]. (א) האם ההוכחה הדוקה ביחס לאלגוריתם? כן — זה משפט 2. (ב) האם האלגוריתם הדוק ביחס לבעיה, כלומר האם קיים אלגוריתם קירוב טוב מ-$2$ ל-$\mathrm{VC}$? זו בעיה פתוחה ותחום מחקר חי. שאלה (א) היא שאלה על הניתוח שלנו; שאלה (ב) היא שאלה על טבע הבעיה, ואיננו עונים עליה בקורס. שימו לב גם: כל אלגוריתם $2$-קירוב הוא בפרט אלגוריתם $4$-קירוב — אי-השוויון רק נחלש [00:35:19].

משפט 3: קיים אלגוריתם קירוב ביחס $\tfrac12$ לבעיית MAXCUT

האלגוריתם (עמוד 3 בסיכום) — חיפוש מקומי. על קלט $G=(V,E)$:

1. אתחל $U \leftarrow \emptyset$ (ולכן $\bar U \leftarrow V$).
2. כל עוד יש קודקוד $v$ שהעברתו מ-$U$ ל-$\bar U$, או מ-$\bar U$ ל-$U$, מגדילה את גודל החתך המושרה:
   1. העבר את הקודקוד.
3. החזר את $U$.

טענה א (פיזביליות). האלגוריתם מחזיר קבוצת קודקודים $U \subseteq V$, וכל קבוצת קודקודים היא פתרון אפשרי ל-$\mathrm{MAXCUT}$. לכן הפלט אפשרי, תמיד. $\blacksquare$

הערה [00:38:30]: כאן, בניגוד ל-$\mathrm{VC}$, אין שום תנאי על הקבוצה המוחזרת — "מקסימלי" הוא חלק מפונקציית המטרה, לא מהגדרת הפתרון האפשרי. לכן כל ההתעקבות תהיה על יחס הקירוב.

טענה ב (עצירה וזמן ריצה). האלגוריתם עוצר לאחר לכל היותר $|E|+1$ סריקות, וזמן הריצה הכולל הוא $O(|G|^2)$ — פולינומי בגודל הקלט.

הוכחה. החשש האמיתי כאן אינו הזמן אלא העצירה [00:41:59]: לכאורה קודקוד יכול לעבור לצד אחד ואז לחזור, ולהיתקע בלולאה אינסופית. ואכן, קודקוד יכול לחזור (ראו דוגמה 4 בהמשך) — אבל זה לא משנה, כי יש לנו "חוש התקדמות" מונוטוני:

בכל איטרציה שבה מבוצעת העברה, גודל החתך המושרה על ידי $U$ גדל בלפחות $1$ — זה בדיוק תנאי הלולאה, ולכן החתך לעולם אינו קטן. גודל החתך מתחיל ב-$0$ (כי $U=\emptyset$), ובאף חתך אין יותר מ-$|E|$ קשתות. לכן מספר ההעברות הוא לכל היותר $|E|$, ומספר הסריקות (כולל הסריקה האחרונה שבה לא נמצא קודקוד משפר ולכן האלגוריתם עוצר) הוא לכל היותר $|E|+1$.

עלות סריקה אחת: עוברים על כל קודקוד $v$, ולכל אחד על כל שכניו, וסופרים כמה מהם בצד שלו וכמה בצד הנגדי; אם בצד שלו יש יותר — מעבירים אותו. בייצוג ברשימת שכנויות זהו מעבר על כל הגרף, כלומר $O(|V|+|E|)$. סך הכל $O(|E| \cdot (|V|+|E|)) = O(|G|^2)$, פולינומי בגודל הקלט. $\blacksquare$

טענה ג (יחס הקירוב). נסמן ב-$K$ את גודלו של חתך מקסימלי ב-$G$, וב-$F$ את קבוצת הקשתות בחתך המושרה על ידי ה-$U$ שהאלגוריתם החזיר. אז $|F| \;\ge\; \tfrac12 |E| \;\ge\; \tfrac12 K .$

הוכחה. נתחיל מהחסם העליון הפשוט על האופטימום: כל חתך הוא תת-קבוצה של $E$, ולכן $K \le |E|$. זהו גודל העזר בבעיית מקסימיזציה — בדיוק המראה של $|F| \le |C_{\mathrm{opt}}|$ ממשפט 1, רק שכאן צריך חסם מלמעלה על $\mathrm{OPT}$ [00:50:01].

כעת שלושה מרכיבים:

(1) פירוק הדרגה. לכל $v \in V$, כל קשת סמוכה ל-$v$ היא או בחתך או לא, ולכן $\mathrm{cut}(v) + \mathrm{other}(v) = \deg_G(v).$ סכימה על כל הקודקודים ושימוש במשפט הדרגות: $\sum_{v\in V}\bigl(\mathrm{cut}(v)+\mathrm{other}(v)\bigr) \;=\; \sum_{v \in V}\deg_G(v) \;=\; 2|E| .$

(2) תנאי האופטימליות המקומית. האלגוריתם עצר. נסמן ב-$\mathrm{cut}(v), \mathrm{other}(v)$ את הערכים ברגע העצירה [01:00:37]. אילו היה קיים $v$ עם $\mathrm{cut}(v) < \mathrm{other}(v)$, אז העברת $v$ לצד הנגדי הייתה הופכת את כל הקשתות הפנימיות שלו לקשתות חתך ולהפך, ומשנה את גודל החתך ב-$\mathrm{other}(v) - \mathrm{cut}(v) > 0$ — כלומר מגדילה אותו, והאלגוריתם לא היה עוצר. סתירה. לכן $\mathrm{cut}(v) \;\ge\; \mathrm{other}(v) \qquad \text{for all } v \in V .$

(3) ספירה כפולה של קשתות החתך. כל קשת בחתך היא בעלת קצה אחד בדיוק ב-$U$ וקצה אחד בדיוק ב-$\bar U$. לכן בסכימה על צד אחד בלבד, כל קשת חתך נספרת בדיוק פעם אחת: $\sum_{v \in U}\mathrm{cut}(v) \;=\; |F|, \qquad \sum_{v \in \bar U}\mathrm{cut}(v) \;=\; |F| .$ מכיוון ש-$V = U \,\dot\cup\, \bar U$, חיבור שתי המשוואות נותן $\sum_{v \in V}\mathrm{cut}(v) \;=\; 2|F| .$

החיבור (ה"גרנד פינלה" [00:57:07]). נשתמש ב-(1), ואז ב-(2) איבר-איבר, ואז ב-(3): $2|E| \;=\; \sum_{v\in V}\bigl(\mathrm{cut}(v)+\mathrm{other}(v)\bigr) \;\le\; \sum_{v\in V} 2\,\mathrm{cut}(v) \;=\; 2\sum_{v\in V}\mathrm{cut}(v) \;=\; 4|F| .$ מכאן $|F| \ge \tfrac12 |E|$, ומכיוון ש-$K \le |E|$ מתקיים גם $|F| \ge \tfrac12 K$. יחד עם טענה א וטענה ב, זהו אלגוריתם קירוב ביחס $\tfrac12$ ל-$\mathrm{MAXCUT}$. $\blacksquare$

הערה [00:57:53]: בהרצאה נאמר לרגע "גדול שווה" ומיד תוקן ל"קטן שווה". הכיוון הנכון הוא זה שכתוב כאן: מחליפים $\mathrm{other}(v)$ ב-$\mathrm{cut}(v)$ שהוא גדול ממנו, ולכן הסכום רק גדל.

הערה: היכן ההפסד בניתוח. החסם $K \le |E|$ הוא גס. על גרף המשולש למשל $|E|=3$ ו-$K=2$, כך שהניתוח מבטיח רק $|F| \ge 1.5$ בעוד שהאלגוריתם למעשה מוצא חתך בגודל $2$, כלומר אופטימלי. שאלת ההידוק של $\tfrac12$ לא נדונה בהרצאה ואינה בסיכום.

משפט 4: לכל $\alpha \ge 1$ — אם ניתן לקרב את בעיית הסוכן הנוסע הכללית ביחס $\alpha$, אז $\mathrm{P}=\mathrm{NP}$

רקע לניסוח [01:03:27]: אין באמת "קושי" מוכח בעולם ה-NP. לא הוכחנו שאי אפשר לפתור בעיה NP-קשה ביעילות; הוכחנו רק שהיא קשה ביחס לשאר בעיות $\mathrm{NP}$. לכן, ובפרט לבעיות אופטימיזציה שעבורן NP-קושי לא מוגדר פורמלית (הוא מוגדר דרך רדוקציות בין שפות, כלומר בעיות הכרעה), התוצאות שאנחנו יכולים לנסח הן תוצאות קושי מותנות: "אם אפשר לעשות X, אז $\mathrm{P}=\mathrm{NP}$" — ומכיוון שאיננו מצפים ל-$\mathrm{P}=\mathrm{NP}$, איננו מצפים ש-X אפשרי.

הוכחה. יהי $\alpha \ge 1$, ונניח בשלילה שקיים אלגוריתם קירוב $A$ ביחס $\alpha$ לגרסת האופטימיזציה של בעיית הסוכן הנוסע. נבנה את האלגוריתם הבא, שמקבל גרף לא מכוון $G=(V,E)$:

1. בנה גרף שלם $\hat G = (V, \hat E)$ על אותה קבוצת קודקודים, ולכל $e \in \hat E$ הגדר $w(e) = \begin{cases} 1 & e \in E \\ \alpha|V|+1 & e \notin E \end{cases}$
2. הרץ את אלגוריתם הקירוב $A$ על $(\hat G, w)$.
3. אם ערך הפתרון שחזר קטן או שווה $\alpha|V|$ — קבל; אחרת — דחה.

הערה [01:11:40]: זו כמעט אותה בנייה כמו הרדוקציה $\mathrm{UHC} \le_p \mathrm{TSP}$ משיעור 12, אבל שם המשקלים היו $1$ ו-$2$ וכאן המשקל של "קשת שלא הייתה" הוא ענק. הענק הזה הוא מה שקונה לנו את הפער מול $\alpha$.

הערה [01:16:56]: האובייקט שבנינו אינו רדוקציית מיפוי. זה אלגוריתם שקורא לאלגוריתם אחר כתת-שגרה ואז מפרש את התשובה — בדיוק סוג ה"רדוקציה" שמכירים מקורסי אלגוריתמים ומבני נתונים. לכן הניסוח הוא "האלגוריתם מכריע את $\mathrm{UHC}$", ולא "יש רדוקציה".

ניתוח זמן ריצה. יהי $G=(V,E)$.

• שלב 1 דורש $O(|V|^2)$ צעדים: יש $\binom{|V|}{2}$ קשתות בגרף השלם, ולכל אחת בדיקה אם היא ב-$E$ וכתיבת משקל. המשקל $\alpha|V|+1$ ניתן לכתיבה ב-$O(\log(\alpha|V|))$ ביטים — זה מספר גדול, אבל קצר [01:12:10]; זה בדיוק ההבדל בין "מספר גדול" ל"מספר שאי אפשר לכתוב".
• שלב 2 דורש זמן פולינומי ב-$|(\hat G,w)|$, כי אלגוריתם קירוב הוא מעצם ההגדרה אלגוריתם פולינומי [01:14:18]. מכיוון ש-$|(\hat G, w)| \le O(|G|^2)$, ומכיוון שפולינום בפולינום הוא פולינום, שלב 2 פולינומי ב-$|G|$.
• שלב 3 דורש זמן קבוע: השוואת שני מספרים.

סך הכל: זמן ריצה פולינומי ב-$|G|$.

ניתוח נכונות. יהי $G=(V,E)$ ונסמן $n = |V|$.

כיוון ראשון: $G \in \mathrm{UHC}$. אז קיים ב-$G$ מעגל המילטוני $C_0$. אותו מעגל קיים גם ב-$\hat G$ (כי $E \subseteq \hat E$), וכל קשתותיו הן קשתות של $E$ ולכן במשקל $1$ כל אחת. במעגל המילטוני יש בדיוק $n$ קשתות, ולכן $w(C_0) = n$. יתרה מזו, כל מעגל המילטוני מורכב מ-$n$ קשתות שמשקל כל אחת הוא לפחות $1$, ולכן $\mathrm{OPT}(\hat G,w) \ge n$; יחד, $\mathrm{OPT}(\hat G,w) = n$ בדיוק. מכיוון ש-$A$ הוא אלגוריתם קירוב ביחס $\alpha$ לבעיית מינימיזציה, הפתרון שהוא מחזיר מקיים $w(A(\hat G,w)) \;\le\; \alpha \cdot \mathrm{OPT}(\hat G,w) \;=\; \alpha n .$ לכן שלב 3 מקבל את $G$ — כנדרש.

כיוון שני: $G \notin \mathrm{UHC}$. אז אין ב-$G$ מעגל המילטוני. יהי $C$ מעגל המילטוני כלשהו ב-$\hat G$ (קיים כזה, כי $\hat G$ שלם). מכיוון ש-$C$ אינו מעגל המילטוני של $G$, בהכרח יש בו קשת $e^* \notin E$, ולכן $w(e^*) = \alpha n + 1$. שאר $n-1$ הקשתות של $C$ תורמות לפחות $1$ כל אחת, ולכן $w(C) \;\ge\; (\alpha n + 1) + (n-1) \;=\; \alpha n + n \;>\; \alpha n .$ זה נכון לכל מעגל המילטוני ב-$\hat G$, ובפרט למעגל המינימלי, ולכן $\mathrm{OPT}(\hat G,w) > \alpha n$. אלגוריתם הקירוב מחזיר פתרון אפשרי, ופתרון אפשרי אינו יכול להיות זול מהאופטימום, ולכן גם $w(A(\hat G,w)) \ge \mathrm{OPT}(\hat G,w) > \alpha n$. לכן שלב 3 דוחה את $G$ — כנדרש.

הערה [01:23:52]: שימו לב שהשתמשנו בשני צדדיו של אי-השוויון שבהגדרת אלגוריתם הקירוב. בכיוון הראשון השתמשנו בצד ה"מעניין" ($\mathrm{ALG} \le \alpha\,\mathrm{OPT}$), ובכיוון השני דווקא בצד הטריוויאלי ($\mathrm{ALG} \ge \mathrm{OPT}$), שנובע מכך שהפלט הוא פתרון אפשרי. בלי הדרישה שהפלט יהיה פיזבילי, הכיוון השני היה נופל.

סיום. האלגוריתם שבנינו מכריע את $\mathrm{UHC}$ בזמן פולינומי, ולכן $\mathrm{UHC} \in \mathrm{P}$. אך $\mathrm{UHC}$ היא NP-קשה (שיעור 12), ולכן לכל $L \in \mathrm{NP}$ מתקיים $L \le_p \mathrm{UHC} \in \mathrm{P}$, כלומר $\mathrm{NP} \subseteq \mathrm{P}$. יחד עם ההכלה הטריוויאלית $\mathrm{P} \subseteq \mathrm{NP}$ נקבל $\mathrm{P} = \mathrm{NP}$. $\blacksquare$

הערה טכנית (לא נאמרה בהרצאה): אם $\alpha$ אינו שלם, $\alpha n + 1$ אינו מספר שלם. אפשר לעבוד עם משקלים רציונליים (ואז $\alpha$ חייב להיות רציונלי כדי שנוכל בכלל לכתוב אותו בזמן פולינומי), או להשתמש במשקל $\lceil \alpha n\rceil + 1$; אז $w(C) \ge \lceil\alpha n\rceil + 1 + (n-1) > \alpha n$ וההוכחה עוברת מילה במילה.

הערה (לא נאמרה בהרצאה): המשקלים שבנינו מפרים בגסות את אי-שוויון המשולש — קשת "יקרה" בין שני קודקודים שיש ביניהם מסלול זול. לכן המשפט אומר דבר על TSP הכללי בלבד, ואינו סותר את קיומם של אלגוריתמי קירוב לגרסה המטרית.

מסקנה: שקילות [01:25:28]. למעשה מתקיים: $\exists\,\alpha \ge 1 \text{ approximation for general } \mathrm{TSP} \iff \mathrm{P}=\mathrm{NP} .$ הכיוון שהוכחנו הוא ($\Rightarrow$). הכיוון ($\Leftarrow$) מיידי: אם $\mathrm{P}=\mathrm{NP}$ אז אפשר להכריע את גרסת ההכרעה של TSP בזמן פולינומי, ובאמצעות חיפוש בינארי על ערך המטרה גם לפתור את גרסת האופטימיזציה במדויק — כלומר לקרב אותה בפקטור $1$; ואם אפשר לקרב בפקטור $1$, אז בפרט אפשר בפקטור $3$ או בכל $\alpha \ge 1$ אחר.

דוגמאות ותרגילים מהשיעור

דוגמה 1: הרצת אלגוריתם ה-VC על מסלול באורך 3 — הסדר קובע

יהי $G$ המסלול $a - b - c - d$, כלומר $E = \{ab, bc, cd\}$. הכיסוי המינימלי הוא $\{b,c\}$ בגודל $2$.

סדר א' (הקשת הנבחרת ראשונה היא $bc$): $C=\{b,c\}$, $F=\{bc\}$; מוחקים את $b,c$ ואיתם את $ab, bc, cd$. לא נשארו קשתות. הפלט: $C=\{b,c\}$, גודל $2$. יחס: $2/2 = 1$.

סדר ב' (הקשת הנבחרת ראשונה היא $ab$): $C=\{a,b\}$, $F=\{ab\}$; מוחקים את $a,b$ ואיתם את $ab,bc$. נשארה $cd$. איטרציה שנייה: $C=\{a,b,c,d\}$, $F=\{ab,cd\}$. הפלט בגודל $4$. יחס: $4/2 = 2$.

מה למדנו: האלגוריתם אינו קובע איזו קשת לבחור, והפלט תלוי בבחירה — אבל בשני המקרים מתקיים $|F| \le |C_{\mathrm{opt}}|$ ו-$|C|=2|F|$, ולכן החסם $|C| \le 2|C_{\mathrm{opt}}|$ נשמר תמיד.

דוגמה 2: הרצה על המעגל $C_6$

$V=\{1,\dots,6\}$, $E=\{12,23,34,45,56,16\}$. הכיסוי המינימלי הוא $\{1,3,5\}$ בגודל $3$.

• איטרציה 1: בוחרים $12$. $C=\{1,2\}$, $F=\{12\}$. מוחקים $1,2$ ואיתם $12,23,16$. נשאר $E'=\{34,45,56\}$.
• איטרציה 2: בוחרים $34$. $C=\{1,2,3,4\}$, $F=\{12,34\}$. מוחקים $3,4$ ואיתם $34,45$. נשאר $E'=\{56\}$.
• איטרציה 3: בוחרים $56$. $C=\{1,\dots,6\}$, $F=\{12,34,56\}$. אין קשתות.

פלט: כל ששת הקודקודים. בדיקה: $|F|=3 \le |C_{\mathrm{opt}}|=3$ ✓, $|C|=6=2|F|$ ✓, $6 \le 2\cdot 3$ ✓ — היחס כאן הדוק בדיוק.

תרגיל 3 (שאלת סטודנט, [00:16:38]–[00:18:13]): למה לא להוסיף רק קצה אחד?

השאלה. האלגוריתם "מבזבז": הוא מכניס שני קודקודים לכל קשת. למה לא לבחור קשת $e=xy$, להוסיף רק את $x$ ל-$C$, ולמחוק רק את $x$ (ואיתו את הקשתות הנוגעות בו)?

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

נתבונן בכוכב $K_{1,n}$: קודקוד מרכזי $c$ ו-$n$ עלים $x_1,\dots,x_n$, כאשר $E=\{cx_i\}$. הכיסוי המינימלי הוא $\{c\}$, כלומר $|C_{\mathrm{opt}}|=1$.

מכיוון שהאלגוריתם דטרמיניסטי אך אינו מגדיר את סדר בחירת הקשתות, אפשר לבנות קלט (או מימוש) שבו הבחירה תמיד "רעה": בכל איטרציה נבחרת קשת $cx_i$ ומוסיפים דווקא את העלה $x_i$. מחיקת $x_i$ מסלקת רק את הקשת $cx_i$, ושאר הקשתות נשארות. לאחר $n$ איטרציות $C=\{x_1,\dots,x_n\}$, כלומר $|C| = n = |V|-1 \quad\text{while}\quad |C_{\mathrm{opt}}| = 1 .$ היחס הוא $|V|-1$, שגדל עם הקלט — כלומר אין $\alpha$ קבוע שהאלגוריתם הזה מקיים.

המסקנה המבנית. מחיקת שני הקצוות אינה בזבוז; היא בדיוק מה שהופך את $F$ לזיווג, ובלעדיה הפונקציה $\varphi$ שבהוכחת משפט 1 מפסיקה להיות חד-חד-ערכית. המרצה הוסיף שאותה תופעה מופיעה גם על מסלול ארוך [00:17:09].

תרגיל 4 (מהשיעור, [00:33:12]): הראו שהאלגוריתם ל-VC אינו יכול להשיג יחס טוב מ-$2$

זהו בדיוק משפט 2 לעיל: משפחת הזיווגים המושלמים $M_n$. פתרון מלא ניתן שם.

דוגמה 5: הרצת אלגוריתם ה-MAXCUT — קודקוד שעובר וחוזר

החשש שהמרצה העלה [00:41:59] הוא שקודקוד יעבור הלוך ושוב לנצח. הנה גרף שבו קודקוד באמת חוזר, ובכל זאת האלגוריתם עוצר:

$V = \{v,a,b,p_1,p_2,q_1,q_2\}$, $E = \{va,\;vb,\;ap_1,\;ap_2,\;bq_1,\;bq_2\}$ — עץ עם $|E|=6$.

התחלה: $U=\emptyset$, גודל החתך $0$.

באיטרציה 4 הקודקוד $v$ חוזר ל-$\bar U$: אחרי ש-$a$ ו-$b$ עברו, שתי הקשתות $va,vb$ הפכו לפנימיות, ולכן משתלם להחזיר את $v$. בסיום: $U=\{a,b\}$, כל שש הקשתות חוצות, ואין קודקוד משפר ($\mathrm{cut}(a)=3, \mathrm{other}(a)=0$; $\mathrm{cut}(p_1)=1,\mathrm{other}(p_1)=0$ וכו').

מה למדנו: אי אפשר לטעון "קודקוד לא יחזור"; אפשר לטעון שגודל החתך $0 \to 2 \to 3 \to 4 \to 6$ עולה ממש בכל צעד, וזה לבדו מבטיח עצירה תוך $\le |E|$ העברות. סדרת החתכים היא ה"חוש התקדמות" של האלגוריתם.

בדיקת ההבטחה: $|F| = 6 \ge \tfrac12|E| = 3$ ✓ (וכאן אפילו נמצא האופטימום, $K=6$, כי העץ דו-צדדי).

דוגמה 6: ספירת החתך משני צדדיו [01:01:41]

הדוגמה שהמרצה צייר כדי להסביר את שלב (3) בהוכחת משפט 3: חתך שבו קשתותיו נספרות מצד $U$ כ-$1+1+1+1+1 = 5$, ומצד $\bar U$ כ-$2+2+1 = 5$. אותו חתך, שתי ספירות שונות, אותו מספר — כי כל קשת חוצה נספרת בדיוק פעם אחת בכל אחד מהסכומים, לפי הגדרת החתך. זהו גם ההסבר לכך ש-$\sum_{v\in V}\mathrm{cut}(v) = 2|F|$ ולא $|F|$.

דוגמה 7: הרצת אלגוריתם ההכרעה של משפט 4 עם $\alpha=2$

מופע חיובי. $G$ = המעגל $1-2-3-4-1$, כלומר $V=\{1,2,3,4\}$, $E=\{12,23,34,41\}$. בונים $\hat G = K_4$; המשקלים: $w(12)=w(23)=w(34)=w(41)=1$, ולאלכסונים $w(13)=w(24)=\alpha|V|+1 = 2\cdot4+1 = 9$. המעגל $1-2-3-4-1$ במשקל $4$, וזהו $\mathrm{OPT}$. אלגוריתם קירוב ביחס $2$ חייב להחזיר מעגל במשקל $\le 8$. סף ההכרעה הוא $\alpha|V| = 8$, ולכן האלגוריתם מקבל — נכון, כי $G \in \mathrm{UHC}$.

מופע שלילי. $G$ = המסלול $1-2-3-4$, כלומר $E=\{12,23,34\}$; אין בו מעגל המילטוני. שוב $\hat G=K_4$ ו-$w(12)=w(23)=w(34)=1$, $w(13)=w(14)=w(24)=9$. שלושת המעגלים ההמילטוניים ב-$K_4$:

• $1\!-\!2\!-\!3\!-\!4\!-\!1$: $1+1+1+9 = 12$;
• $1\!-\!2\!-\!4\!-\!3\!-\!1$: $1+9+1+9 = 20$;
• $1\!-\!3\!-\!2\!-\!4\!-\!1$: $9+1+9+9 = 28$.

$\mathrm{OPT} = 12 > 8$, וכל פתרון שיוחזר יהיה לפחות $12$. לכן האלגוריתם דוחה — נכון, כי $G \notin \mathrm{UHC}$.

שימו לב לפער: בכיוון החיובי הערך המקסימלי האפשרי הוא $8$, ובכיוון השלילי הערך המינימלי האפשרי הוא $12$. הפער הזה הוא כל תפקידו של המשקל הענק $\alpha|V|+1$ — הוא נבנה כך שאפילו אלגוריתם קירוב גרוע ככל האפשר לא יוכל "לחצות" את הסף.

הערות מהשיעור

• [00:03:43]–[00:05:49] — "למה דווקא זה?" היא לא השאלה הנכונה עכשיו. המרצה הקדיש כמה דקות לנקודה מתודית: כשרואים אלגוריתם או רדוקציה, סדר הפעולות הוא (1) להבין איך הוא עובד — הרצה יבשה על גרף; (2) להוכיח למה הוא מקיים את מה שדרוש; ורק אחר כך, אם בכלל, לשאול איך מישהו חשב עליו. "זה יכול לקחת חודשים של מחקר. אם אין לכם את החודשים לשבת על זה, לא תגיעו לזה — ואתם גם לא צריכים לצורך הקורס."
• [00:09:33] — ניתוח גס מכוון. "אני קצת הורס את כל מה שלימדו אתכם באלגוריתמים ומבני נתונים": כאן לא מחפשים את זמן הריצה הטוב ביותר אלא רק פולינומיות, ולכן ניתוח גס עדיף כי הוא קצר ובטוח יותר. הניתוח ההדוק ($O(|E|)$ ל-VC) נכון ואף "מעולה", פשוט מיותר.
• [00:20:56]–[00:21:59] — "פתרון אופטימלי", לא "הפתרון האופטימלי". יש גודל אופטימלי אחד (מינימום קיים תמיד בקבוצה לא ריקה של טבעיים), אבל פתרונות אופטימליים יכולים להיות רבים. לכן הסימון הוא "$C_{\mathrm{opt}}$ פתרון אופטימלי", ובניתוח לא מסתמכים על יחידות. משפט 2 מדגים זאת: שם יש $2^{|V|/2}$ פתרונות אופטימליים.
• [00:26:19]–[00:28:25] — שובך היונים. סטודנטים ביקשו לחזור על המעבר $|F| \le |C_{\mathrm{opt}}|$. הניסוח שהוסכם: אם ב-$A$ יש יותר איברים מב-$B$, אז אף פונקציה מ-$A$ ל-$B$ אינה חד-חד-ערכית (שובך היונים); בקונטרפוזיציה — אם קיימת פונקציה חד-חד-ערכית מ-$A$ ל-$B$ אז $|A| \le |B|$. "אתם צריכים לדעת את זה."
• [00:29:31]–[00:30:04] — $|C|=2|F|$ אינו "כמו קודם". סטודנט שאל מתי אמרנו ש-$|C|=2|F|$. התשובה: זו טענה חדשה, ולא משהו שנאמר קודם; היא כמעט מיידית מהבנייה (כל קשת שנכנסה ל-$F$ הכניסה שני קודקודים ל-$C$), אבל היא עדיין טענה שצריך לומר.
• [00:30:36]–[00:31:09] — האם $2$ הוא הקירוב הטוב ביותר ל-VC? שאלה שנשאלה בשיעור הקודם. התשובה: להוכיח שקירוב מסוים הוא הטוב ביותר האפשרי הוא נושא קשה מלא בבעיות פתוחות, ועבור $\mathrm{VC}$ זו בעיה פתוחה לגמרי. תיאורטית ייתכן שקיים אלגוריתם עם יחס $1+\varepsilon$. "התחום עדיין חי — עדיין מוצאים אלגוריתמי קירוב טובים יותר לכל מיני בעיות."
• [00:35:19] — יחס קירוב הוא חסם, לא ערך. אלגוריתם $2$-קירוב הוא בפרט $4$-קירוב; אי-השוויון פשוט נחלש. לכן ההצהרה "יחס הקירוב הוא $2$" משמעה "לכל היותר $2$".
• [00:36:24] — מקסימיזציה: היחס בין $0$ ל-$1$. אזהרה מפורשת: להחזיר פתרון חוקי אבל זעיר (למשל קודקוד בודד ל-Independent Set) אינו קירוב.
• [00:41:59]–[00:44:32] — החשש הראשון בחיפוש מקומי הוא תמיד עצירה. "בדרך כלל כשרואים את האלגוריתם הזה, הדבר הראשון שעולה זה: איך אני יודע שזה עוצר?" והתשובה תמיד: מהו ה-sense of progress, והאם ההתקדמות הזו גוררת חסם על מספר האיטרציות.
• [00:47:19]–[00:48:20] — מה בדיוק עושים בסריקה. לכל קודקוד עוברים על כל שכניו וסופרים כמה מהם בצד שלו וכמה בצד הנגדי; אם בצד שלו יש יותר — מעבירים. בייצוג ברשימת שכנויות זה מעבר על כל הגרף. המרצה ציין שאפשר גם ניתוח מדויק יותר ($|V|\cdot|E|$ או $|G|^3$) — לא משנה, כל אלה פולינומיים.
• [01:03:27]–[01:04:33] — למה בכלל "תוצאות קושי מותנות". "אנחנו קוראים לבעיה NP-קשה, אבל לא באמת הוכחתי שהיא קשה — הוכחתי שהיא קשה ביחס לבעיות ב-$\mathrm{NP}$." לכן כל טענת אי-קירוב בקורס היא מהצורה "אם ניתן לקרב, אז $\mathrm{P}=\mathrm{NP}$".
• [01:08:26]–[01:09:32] — איך מוכיחים $\mathrm{P}=\mathrm{NP}$ תחת הנחה. אפשרות א': לקחת $A \in \mathrm{NP}$ שרירותית ולהראות $A \in \mathrm{P}$ — קשה. אפשרות ב', והדרך שנבחרה: לקחת בעיה אחת שידועה כ-NP-קשה ולהראות שהיא ב-$\mathrm{P}$; מהגדרת NP-קושי נובע מיד ש-$\mathrm{NP} \subseteq \mathrm{P}$. "עכשיו העניין הוא רק לבחור נכון את הבעיה ה-NP-קשה שנוח לעבוד איתה" — וכאן בחרנו את $\mathrm{UHC}$, כי גרסת האופטימיזציה של TSP נבנתה עליה מלכתחילה.
• [01:12:10] — מספר גדול אינו מספר ארוך. המשקל $\alpha|V|+1$ הוא ענק, אבל אורכו $O(\log(\alpha|V|))$ ביטים. זו נקודה שחוזרת בכל הקורס (ראו גם SUBSET-SUM בשיעור 11): מה שמגביל אותנו הוא אורך הייצוג, לא הערך.
• [01:19:36]–[01:21:45] — בלבול נפוץ שהמרצה פתר בכיתה. ב-$\hat G$ תמיד קיים מעגל המילטוני (הוא גרף שלם) — זה לא מה שמעניין; מה שמעניין הוא המשקל שלו. ובנוסף: משקל המעגל הוא סכום על $|V|$ קשתות בלבד, ולא על כל קשתות הגרף השלם.
• [01:25:28] — למה חשוב לומר "שקול". התוצאה אינה רק "קירוב ⟸ $\mathrm{P}=\mathrm{NP}$" אלא שקילות, כי אם $\mathrm{P}=\mathrm{NP}$ אפשר לפתור את הבעיה במדויק ובפרט לקרב אותה בכל פקטור. הכיוון הזה מיידי, ובכל זאת צריך לומר אותו כדי לטעון שקילות.