25חזרה לקראת המבחן: תת-גרף מקסימלי חסר מעגלים, כיסוי בהיפרגרף 3-אחיד, חתך מכוון ואי-קירוב של Bin-Packing

בקצרה

• זהו שיעור חזרה: ארבעה תרגילים מתרגיל בית 3, כל אחד נפתר על הלוח מקצה לקצה. אין כאן תיאוריה חדשה — יש כאן את התבניות שבהן הקורס בודק את החומר.
• שלושת הדברים שכל אלגוריתם קירוב חייב חוזרים בכל תרגיל ומודגשים שוב ושוב: (1) זמן ריצה פולינומי, (2) הפלט הוא פתרון אפשרי, (3) יחס הקירוב. הפריט (2) הוא זה שנשכח הכי הרבה.
• תרגיל 3 — פירוק קשתות גרף מכוון לפי סדר האינדקסים לשתי קבוצות חסרות מעגלים, ובחירת הגדולה מביניהן: אלגוריתם קירוב ביחס $\tfrac12$ לבעיית תת-הגרף המקסימלי חסר המעגלים.
• תרגיל 4 — הכללה של הכיסוי בקודקודים להיפרגרפים 3-אחידים: (א) $\mathrm{VC}\le_p\mathrm{3H\text{-}VC}$, ולכן $\mathrm{3H\text{-}VC}$ היא NP-קשה; (ב) אותו אלגוריתם חמדני של שיעור 13, עם $3$ במקום $2$ — אלגוריתם קירוב ביחס $3$.
• תרגיל 5 — חתך מקסימלי בגרף מכוון: מוחקים כיוונים, מריצים את אלגוריתם ה-$\tfrac12$ ל-$\mathrm{MAXCUT}$, ואז בוחרים בין $U$ ל-$\bar U$. יחס $\tfrac14$. זהו התרגיל שרוב הכיתה טעתה בו — בהגשה הוחזר ניתוח בתוחלת, וזה אינו אלגוריתם קירוב.
• תרגיל 7 — אם קיים אלגוריתם קירוב ביחס $1.49$ ל-$\mathrm{BIN\text{-}PACKING}$ אז $\mathrm{P}=\mathrm{NP}$. אותה תבנית בדיוק כמו אי-הקירוב של $\mathrm{TSP}$ משיעור 13: מניחים אלגוריתם קירוב, בונים ממנו אלגוריתם הכרעה לבעיה NP-קשה, ומסיקים.
• הסף $1.49$ אינו שרירותי: כל $\alpha<\tfrac32$ עובד, ובדיוק $\tfrac32$ כבר לא — כי מספר התאים הוא מספר שלם.

רקע ותלויות

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

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

2. הכיסוי בקודקודים (שיעור 10, הגדרה 1 ומשפט 2). $U\subseteq V$ היא כיסוי בקודקודים של $G=(V,E)$ אם $\forall e\in E:\ e\cap U\ne\emptyset$, והשפה היא $\mathrm{VC}=\{\langle G,k\rangle \mid \exists\,U\subseteq V \text{ vertex cover},\ |U|\le k\}.$ $\mathrm{VC}$ היא NP-שלמה (שיעור 10, משפט 2, דרך $\mathrm{IS}\le_p\mathrm{VC}$).

3. אלגוריתם ה-$2$-קירוב ל-$\mathrm{VC}$ (שיעור 13, משפט 1). כל עוד יש קשת $e=xy$ בגרף — מכניסים את שני קצותיה ל-$C$, מוסיפים את $e$ ל-$F$, ומוחקים את $x,y$ ואת כל הקשתות הנוגעות בהם. הניתוח: $F$ היא קבוצת קשתות זרות בזוגות, ולכן $|F|\le|C_{\mathrm{opt}}|$; וכן $|C|=2|F|$; ומכאן $|C|\le 2|C_{\mathrm{opt}}|$. תרגיל 4(ב) כאן הוא בדיוק ההכללה של האלגוריתם הזה.

4. אלגוריתם ה-$\tfrac12$-קירוב ל-$\mathrm{MAXCUT}$ (שיעור 13, משפט 3; ובגרסה חמדנית שיעור 14, משפט 1). לשני האלגוריתמים אותה הבטחה: הם רצים בזמן פולינומי, מחזירים $U\subseteq V$, וגודל החתך המושרה מקיים $|F|\;\ge\;\tfrac12|E| \;\ge\;\tfrac12\,\mathrm{OPT}.$ ההוכחה של שיעור 13 מסתמכת על $\mathrm{cut}(v)+\mathrm{other}(v)=\deg(v)$ ועל $\sum_v \deg(v)=2|E|$ — שני הדברים נכונים גם במולטיגרף, ולכן האלגוריתם תקף גם על גרפים עם קשתות מקבילות. זה יהיה קריטי בתרגיל 5.

5. $\mathrm{PARTITION}$ ו-$\mathrm{BIN\text{-}PACKING}$ (שיעור 12). $\mathrm{PARTITION}$ שואלת אם ניתן לפצל $a_1,\dots,a_n$ לשני חלקים שווי-סכום; היא NP-שלמה (משפט 2 שם). $\mathrm{BIN\text{-}PACKING}$ מקבלת $a_1,\dots,a_n\in(0,1]$ ומספר $k$, ושואלת אם ניתן לארוז אותם ב-$k$ תאים בעלי קיבולת $1$; היא NP-שלמה (משפט 4 שם), ונשארת NP-קשה גם כאשר $k=2$ קבוע (משפט 5 שם).

6. תבנית אי-הקירוב (שיעור 13, משפט 4). ההוכחה ש"קירוב בכל יחס קבוע ל-$\mathrm{TSP}$ הכללית גורר $\mathrm{P}=\mathrm{NP}$" היא בדיוק התבנית של תרגיל 7: מניחים אלגוריתם קירוב, קוראים לו כתת-שגרה, ומתרגמים את ערך הפלט לתשובת כן/לא לבעיה NP-קשה. שימו לב שהאובייקט המתקבל אינו רדוקציית מיפוי אלא אלגוריתם הכרעה.

7. הטריק של "החלפת קודקוד חדש בשכן" (שיעור 19, משפט 4). ברדוקציה $\mathrm{VC}\le_p\mathrm{DS}$ הוספנו לכל קשת $xy$ קודקוד חדש $v_{xy}$, ובכיוון ההפוך היינו צריכים להחליף כל קודקוד חדש בקבוצה בקודקוד ישן. תרגיל 4(א) משתמש באותו טריק בדיוק — המרצה קישר בין השניים ב-[00:34:33].

8. כיוון הרדוקציה — בעברית. $A\le_p B$ פירושו: קיימת פונקציה $f$ הניתנת לחישוב בזמן פולינומי כך ש-$x\in A \iff f(x)\in B$. במילים: $B$ היא הבעיה הקשה לפחות כמו $A$ — אלגוריתם יעיל ל-$B$ היה נותן אלגוריתם יעיל ל-$A$. בקובץ הזה נוכיח $\mathrm{VC}\le_p\mathrm{3H\text{-}VC}$, כלומר $\mathrm{3H\text{-}VC}$ היא הקשה מבין השתיים.

הגדרות

הגדרה 1: תת-גרף חסר מעגלים ובעיית האופטימיזציה שלו

יהי $G=(V,E)$ גרף מכוון. תת-קבוצת קשתות $E'\subseteq E$ נקראת חסרת מעגלים אם הגרף $G'=(V,E')$ אינו מכיל מעגל מכוון.

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

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

מופע. על $V=\{1,2,3\}$ עם $E=\{(1,2),(2,3),(3,1)\}$ — מעגל מכוון יחיד — כל תת-קבוצה של שתי קשתות היא פתרון אפשרי, ו-$E$ עצמה אינה. לכן $\mathrm{OPT}=2$.

אי-מופע. $E'=E$ בדוגמה שלמעלה אינו פתרון אפשרי, אף שהוא הגדול ביותר. זו בדיוק הנקודה שבה נופלים: פתרון גדול שאינו פיזבילי אינו פתרון.

הגדרה 2: היפרגרף 3-אחיד וכיסוי קודקודים בו

היפרגרף 3-אחיד הוא זוג $H=(V,E)$ שבו $V$ קבוצת קודקודים ו-$E$ הוא אוסף של תת-קבוצות של $V$ בגודל $3$ כל אחת. כל תת-קבוצה כזו נקראת היפר-קשת.

כיסוי קודקודים של $H$ הוא קבוצה $S\subseteq V$ המקיימת $\forall e\in E:\quad e\cap S\ne\emptyset .$

השפה: $\mathrm{3H\text{-}VC}=\left\{\langle H,k\rangle \;\middle|\; \begin{array}{l} H \text{ a 3-uniform hypergraph},\ k\in\mathbb{N},\\ \exists\,S\subseteq V \text{ a vertex cover of } H,\ |S|\le k\end{array}\right\}$

אינטואיציה. זו הכללה מדויקת של $\mathrm{VC}$: גרף רגיל הוא היפרגרף $2$-אחיד, כי כל קשת לא מכוונת היא בדיוק קבוצה בגודל $2$ של קודקודים ([00:12:40]). ההגדרה של הכיסוי לא השתנתה כלל — אותה שורה $e\cap S\ne\emptyset$ מילה במילה. באופן כללי יותר: יש לנו אוסף תת-קבוצות, ומחפשים קבוצת איברים ה"נוגעת" בכל אחת מהן.

מופע. $V=\{1,2,3,4,5,6\}$, $E=\{\{1,2,3\},\{3,4,5\},\{4,5,6\}\}$. אז $S=\{3,4\}$ הוא כיסוי בגודל $2$: $3$ בשתי ההיפר-קשתות הראשונות, $4$ בשתי האחרונות.

אי-מופע. $S'=\{1\}$ אינו כיסוי של אותו $H$: $\{3,4,5\}\cap S'=\emptyset$.

הערה על "בגודל $k$" מול "בגודל לכל היותר $k$" ([00:40:50]–[00:41:23]). ניסוח התרגיל אומר "קיים ב-$H$ כיסוי קודקודים בגודל $k$". שתי הצורות שקולות כאן, כי על-קבוצה של כיסוי היא כיסוי — אם יש כיסוי בגודל $j\le k\le|V|$ אפשר תמיד להשלים אותו לגודל $k$ בדיוק בהוספת קודקודים שרירותיים. המרצה הדגיש שזה נכון ב-$\mathrm{VC}$, ב-$\mathrm{IS}$ וב-$\mathrm{CLIQUE}$ (שם מורידים איברים במקום להוסיף), אבל לא ב-$\mathrm{MAXCUT}$: שם אני בוחר קודקודים כדי לקבל קשתות, ובמספר הקשתות אין לי שליטה מדויקת. הקובץ הזה כותב את השפה עם $\le k$; כל ההוכחות עוברות מילה במילה גם עם "בדיוק $k$".

הגדרה 3: החתך המושרה בגרף מכוון

יהי $G=(V,E)$ גרף פשוט מכוון ותהי $U\subseteq V$, ונסמן $\bar U=V\setminus U$. החתך המושרה על ידי $U$ הוא $\delta(U)\;=\;\{\,(u,v)\in E \;\mid\; u\in U,\ v\in\bar U\,\},$ כלומר קבוצת הקשתות שזנבן ב-$U$ וראשן ב-$\bar U$.

קלט: גרף פשוט מכוון $G=(V,E)$. פתרונות אפשריים: כל $U\subseteq V$. ערך: $|\delta(U)|$. מטרה: מקסימיזציה.

אינטואיציה — ההבדל מהמקרה הלא מכוון. בגרף לא מכוון $U$ ו-$\bar U$ מגדירות אותו חתך. כאן זה נשבר לחלוטין: $\delta(U)$ סופרת רק את הקשתות שיוצאות מ-$U$, ו-$\delta(\bar U)$ רק את אלה שנכנסות אליה. הא-סימטריה הזו היא כל מה שמייחד את התרגיל, והיא גם המקור לפקטור $\tfrac12$ הנוסף שיעלה לנו במעבר מ-$\tfrac12$ ל-$\tfrac14$.

מופע. $V=\{a,b\}$, $E=\{(a,b)\}$. אז $\delta(\{a\})=\{(a,b)\}$ בגודל $1$, ואילו $\delta(\{b\})=\emptyset$ בגודל $0$. שתי הקבוצות המשלימות זו את זו, ושני החתכים שונים לגמרי — הנה ההבדל בשורה אחת.

אי-מופע. $U=\emptyset$ נותנת $\delta(\emptyset)=\emptyset$ — פתרון אפשרי לגמרי, פשוט גרוע. כמו ב-$\mathrm{MAXCUT}$, כל תת-קבוצת קודקודים היא פיזבילית, ולכן כל העבודה בתרגיל 5 היא ביחס הקירוב.

הגדרה 4: גרסת האופטימיזציה של $\mathrm{BIN\text{-}PACKING}$

קלט: $b_1,\dots,b_n\in(0,1]$. פתרונות אפשריים: כל פונקציה $f:\{1,\dots,n\}\to\{1,\dots,m\}$ (הקצאת פריטים לתאים) המקיימת $\sum_{i:\,f(i)=\ell} b_i\le 1$ לכל $\ell$. ערך: מספר התאים בשימוש. מטרה: מינימיזציה.

אינטואיציה. לכל תא קיבולת $1$; רוצים להשתמש במספר קטן ככל האפשר. שימו לב שהערך הוא מספר שלם — עובדה שנראית טריוויאלית וששוברת את כל התרגיל השביעי לטובתנו.

מופע. $\left(\tfrac13,\tfrac13,\tfrac13,\tfrac12,\tfrac12\right)$ נארז בשני תאים: שלושת השלישים בתא אחד, שני החצאים בשני.

אי-מופע. $\left(\tfrac34,\tfrac34,\tfrac34\right)$ אינו נארז בשני תאים — לפי שובך היונים תא אחד יקבל שניים מהם, וסכומם $\tfrac32>1$.

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

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

משפט 1: $\mathrm{VC}$ היא NP-שלמה

טענה. $\mathrm{VC}$ היא NP-שלמה.

מקור. שיעור 10, משפט 2: $\mathrm{IS}\le_p\mathrm{VC}$ דרך ההבחנה ש-$U$ היא כיסוי בקודקודים אם ורק אם $V\setminus U$ בלתי תלויה, ובצירוף $\mathrm{VC}\in\mathrm{NP}$. אנחנו נשתמש רק ב-NP-קושי, בתרגיל 4(א). $\blacksquare$

משפט 2: $\mathrm{PARTITION}$ היא NP-שלמה, וכך גם $\mathrm{BIN\text{-}PACKING}$ עם $k=2$ קבוע

טענה. $\mathrm{PARTITION}$ NP-שלמה, ובעיית האריזה בשני תאים בעלי קיבולת $1$ (בלי ש-$k$ הוא חלק מהקלט) היא NP-קשה.

מקור. שיעור 12, משפט 2 ($\mathrm{SUBSET\text{-}SUM}\le_p\mathrm{PARTITION}$) ומשפט 5. הרדוקציה של משפט 4 שם שולחת את כל הקלטים לתת-המרחב שבו $k=2$, ולכן אותה רדוקציה עצמה מוכיחה את NP-הקושי של הגרסה עם $k$ קבוע. אנחנו נשתמש בשתיהן בתרגיל 7 — ב-$\mathrm{PARTITION}$ בפתרון הכתוב, ובגרסה עם $k=2$ בקיצור-הדרך שהמרצה הציע. $\blacksquare$

משפט 3: קיים אלגוריתם קירוב פולינומי ביחס $\tfrac12$ ל-$\mathrm{MAXCUT}$, גם במולטיגרפים

טענה. קיים אלגוריתם פולינומי המקבל גרף לא מכוון $\hat G=(V,\hat E)$ — אפשר עם קשתות מקבילות — ומחזיר $U\subseteq V$ שהחתך המושרה על ידה מקיים $|(U,\bar U)|\ge\tfrac12|\hat E|$.

מקור והוכחה. שיעור 13, משפט 3 (חיפוש מקומי), או שיעור 14, משפט 1 (חמדני חד-מעברי). שניהם משיגים את אותה הבטחה. המרצה ציין את שניהם במפורש ב-[01:39:58] ואמר ש"האלגוריתם שראינו בשיעור" בפתרון מתייחס לכל אחד מהם.

הערה: למה זה עובד גם עם קשתות מקבילות ([01:27:23]). ההוכחה של שיעור 13 בנויה משלוש טענות: $\mathrm{cut}(v)+\mathrm{other}(v)=\deg(v)$, אופטימליות מקומית $\mathrm{cut}(v)\ge\mathrm{other}(v)$, וספירה כפולה $\sum_{v}\mathrm{cut}(v)=2|F|$. אף אחת מהשלוש אינה מניחה שהגרף פשוט — כולן ספירות של מופעי קשתות. לכן ההבטחה $|(U,\bar U)|\ge\tfrac12|\hat E|$ תקפה כשסופרים כל קשת מקבילה בנפרד. תרגיל 5 חייב את התכונה הזו. $\blacksquare$

משפט 4: $\mathrm{VC}\le_p\mathrm{3H\text{-}VC}$, ולכן $\mathrm{3H\text{-}VC}$ היא NP-קשה

זהו תרגיל 4(א). הניסוח והוכחתו המלאה נמצאים בדוגמאות ותרגילים, סעיף "תרגיל 4(א)", כי שם מקומו: זו שאלת תרגיל בית שנפתרה על הלוח.

משפט 5: ההשלמה — $\mathrm{3H\text{-}VC}\in\mathrm{NP}$

טענה. $\mathrm{3H\text{-}VC}\in\mathrm{NP}$, ולכן יחד עם משפט 4 היא NP-שלמה.

הוכחה. התרגיל ביקש רק NP-קושי, וההשלמה קלה. ה-certificate הוא הקבוצה $S\subseteq V$ עצמה; אורכה לכל היותר $|V|$ שמות קודקודים ולכן פולינומי בגודל הקלט. המאמת בודק שני דברים: ש-$|S|\le k$, ושלכל $e\in E$ מתקיים $e\cap S\ne\emptyset$. הבדיקה השנייה היא מעבר יחיד על $E$, ולכל היפר-קשת בדיקה של שלושה קודקודים מול $S$ — סך הכול $O(|E|\cdot|S|)$, פולינומי. לפי ההגדרה של $\mathrm{NP}$ דרך מאמת (שיעור 6), $\mathrm{3H\text{-}VC}\in\mathrm{NP}$. $\blacksquare$

הערה: ההשלמה הזו לא נאמרה בהרצאה — התרגיל ביקש NP-קושי בלבד. היא נוספה כאן כי במבחן ניסוח מסוג "הוכיחו כי הבעיה NP-שלמה" הוא נפוץ לפחות כמו "NP-קשה", וההבדל הוא בדיוק השורה הזו.

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

זהו לב הקובץ. ארבעת התרגילים לפי מספורם במקור.

תרגיל 3: תת-גרף מקסימלי חסר מעגלים

הניסוח (כפי שנמסר)

(א) יהי $G=(V,E)$ גרף מכוון עבורו $V=\{1,2,\dots,n\}$. נסמן ב-$E_1$ את קבוצת הקשתות ב-$G$ אשר מכוונות ממספר טבעי למספר טבעי גדול ממנו, כלומר $E_1=\{(i,j)\in E \mid i<j\},$ ונסמן ב-$G_1=(V,E_1)$ את תת-הגרף המתאים של $G$. נסמן ב-$E_2$ את קבוצת הקשתות ב-$G$ אשר מכוונות ממספר טבעי למספר טבעי קטן ממנו, כלומר $E_2=\{(i,j)\in E \mid i>j\},$ ונסמן ב-$G_2=(V,E_2)$ את תת-הגרף המתאים של $G$. הראו שהגרפים $G_1,G_2$ חסרי מעגלים (מכוונים).

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

קלט: גרף מכוון $G=(V,E)$. מטרה: למצוא קבוצת קשתות $E'\subseteq E$ גדולה ככל האפשר, כך שהגרף $G'=(V,E')$ חסר מעגלים.

הציעו אלגוריתם עם זמן ריצה פולינומי אשר משיג יחס קירוב $\tfrac12$ לבעיה. היעזרו בסעיף הקודם.

פתרון (א)

הערה מתודית ([00:01:34]). סעיף (א) הוא טענה קומבינטורית, לא אלגוריתמית. אנחנו לא מציעים אלגוריתם למצוא את $E_1$ — אנחנו מגדירים אותה ומוכיחים עליה תכונה. ההבחנה הזו חשובה, ובסעיף (ב) נעבור בדיוק לצד השני.

נוכיח ש-$G_1$ חסר מעגלים; ההוכחה ל-$G_2$ סימטרית.

נניח בשלילה שקיים ב-$G_1$ מעגל מכוון $v_1\to v_2\to\cdots\to v_k\to v_1,\qquad k\ge 2,$ כלומר $(v_1,v_2),(v_2,v_3),\dots,(v_{k-1},v_k),(v_k,v_1)\in E_1$.

לפי הגדרת $E_1$, כל קשת $(i,j)\in E_1$ מקיימת $i<j$. נפעיל זאת על כל קשתות המעגל בזו אחר זו: $v_1<v_2<v_3<\cdots<v_k .$ מהקשת האחרונה $(v_k,v_1)\in E_1$ נקבל גם $v_k<v_1$. משרשור שני הדברים: $v_1<v_2<\cdots<v_k<v_1,$ ומיחס הסדר החזק על הטבעיים נובע $v_1<v_1$ — סתירה.

לכן ב-$G_1$ אין מעגל מכוון. באופן סימטרי, כל קשת ב-$E_2$ מקיימת $i>j$, מעגל היה נותן $v_1>v_2>\cdots>v_k>v_1$ ולכן $v_1>v_1$, סתירה; ולכן גם $G_2$ חסר מעגלים. $\blacksquare$

על המקרה $k=1$ (לולאה עצמית) ([00:03:21]). המרצה הזכיר את הקונבנציה: אם לא נאמר אחרת, הגרף פשוט; "מכוון" אינו מבטל את "פשוט". לכן אין לולאות $(i,i)$. אבל למעשה אין בכך צורך: לולאה $(i,i)$ אינה מקיימת $i<i$ ואינה מקיימת $i>i$, ולכן אינה שייכת לא ל-$E_1$ ולא ל-$E_2$. הטענה נכונה גם אם מרשים לולאות ב-$G$.

הבחנה שנשתמש בה בסעיף (ב). בגרף פשוט מכוון כל קשת $(i,j)$ מקיימת $i\ne j$, ולכן בדיוק אחד משני התנאים $i<j$, $i>j$ מתקיים. מכאן $E=E_1\,\dot\cup\,E_2,$

ולכן

$|E_1|+|E_2|=|E| .$

פתרון (ב) — האלגוריתם

קלט: גרף מכוון $G=(V,E)$ כאשר $V=\{1,2,\dots,n\}$.

1. $E_1\leftarrow\emptyset$, $E_2\leftarrow\emptyset$.
2. לכל קשת $e=(i,j)\in E$:
   • אם $i<j$ — הכנס את $e$ ל-$E_1$;
   • אחרת — הכנס את $e$ ל-$E_2$.
3. אם $|E_1|\ge|E_2|$ — החזר את $E_1$; אחרת — החזר את $E_2$.

שלושה דברים צריך להוכיח, תמיד ([00:04:56]–[00:06:00]): זמן ריצה פולינומי, פיזביליות הפלט, ויחס הקירוב.

(1) ניתוח זמן ריצה

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

(2) פיזביליות

נסמן ב-$E'$ את הקבוצה שהאלגוריתם מחזיר. לפי שלב 3, $E'\in\{E_1,E_2\}$, ולפי בניית שלב 2 אלה בדיוק הקבוצות מסעיף (א). לפי סעיף (א) שני הגרפים $(V,E_1)$ ו-$(V,E_2)$ חסרי מעגלים, ולכן בכל מקרה $(V,E')$ חסר מעגלים — כלומר $E'$ הוא פתרון אפשרי לבעיה. $\blacksquare$

זה השלב שנשכח ([00:04:24]). התשובה הראשונה בכיתה לשאלה "מה הקבוצה שאני מחזיר צריכה לקיים?" הייתה "לפחות חצי". המרצה עצר: קודם כול היא צריכה להיות פתרון אפשרי, ואת זה צריך גם להוכיח.

(3) יחס הקירוב

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

לפי ההבחנה בסוף סעיף (א), $|E_1|+|E_2|=|E|$. שני מספרים אי-שליליים שסכומם $|E|$ — לפחות אחד מהם גדול או שווה למחצית הסכום: $|E_1|\ge\tfrac12|E|$

או

$|E_2|\ge\tfrac12|E| .$ האלגוריתם מחזיר את הגדולה מבין השתיים, ולכן בכל מקרה $|E'|=\max\{|E_1|,|E_2|\}\;\ge\;\tfrac12|E| .$

מצד שני, $\hat E\subseteq E$ ולכן $|\hat E|\le|E|$ — זהו החסם העליון על האופטימום, ובבעיית מקסימיזציה זה בדיוק מה שדרוש. משרשור: $|E'|\;\ge\;\tfrac12|E|\;\ge\;\tfrac12|\hat E| .$ ומן הצד השני $|E'|\le|\hat E|$, כי $E'$ הוא פתרון אפשרי ו-$\hat E$ אופטימלי. יחד: $\tfrac12|\hat E|\;\le\;|E'|\;\le\;|\hat E| ,$ ולפי הגדרה 3(ב) של שיעור 13 זהו אלגוריתם קירוב ביחס $\tfrac12$ לבעיית תת-הגרף המקסימלי חסר המעגלים. $\blacksquare$

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

תרגיל 4(א): $\mathrm{3H\text{-}VC}$ היא NP-קשה

הניסוח (כפי שנמסר)

היפרגרף 3-אחיד הוא זוג $H=(V,E)$ כאשר $V$ קבוצת קודקודים ו-$E$ אוסף של תת-קבוצות של $V$ בגודל $3$ כל אחת. כל תת-קבוצה כזו נקראת היפר-קשת (בעצם ניתן לחשוב על גרף רגיל כעל היפרגרף 2-אחיד, כיוון שכל קשת היא קבוצת קודקודים בגודל $2$). כיסוי קודקודים של היפרגרף $H$ הוא קבוצה $S\subseteq V$ המקיימת שבכל היפר-קשת ב-$E$ יש קודקוד ששייך ל-$S$, כלומר לכל $e\in E$ מתקיים $e\cap S\ne\emptyset$.

(א) תהא $\mathrm{3H\text{-}VC}$ שפת כל הזוגות $\langle H,k\rangle$ של היפרגרף 3-אחיד $H$ ומספר טבעי $k$ עבורם קיים ב-$H$ כיסוי קודקודים בגודל $k$. הוכיחו כי הבעיה $\mathrm{3H\text{-}VC}$ היא NP-קשה.

הרעיון, ולמה דווקא מ-$\mathrm{VC}$

נראה $\mathrm{VC}\le_p\mathrm{3H\text{-}VC}$ — כלומר, $\mathrm{3H\text{-}VC}$ היא הבעיה הקשה מבין השתיים. הבחירה ב-$\mathrm{VC}$ כבעיית המקור אינה מקרית: היא ה"בעיה הקרובה" ([00:14:49]) — ההגדרה של כיסוי קודקודים בהיפרגרף היא מילה במילה ההגדרה מ-$\mathrm{VC}$. המרצה הציג את זה כשיטת עבודה: הניחוש הראשון הוא תמיד הבעיה הדומה ביותר; אם היא לא עובדת, אז מתחילים לחשוב על אחרות.

הקושי הטכני היחיד: הפלט חייב להיות היפרגרף 3-אחיד, וקשתות של גרף רגיל הן בגודל $2$. צריך "לנפח" כל קשת לגודל $3$ מבלי לשנות את התשובה — ולכן מוסיפים לכל קשת קודקוד חדש משלה.

הרדוקציה (האלגוריתם $R$)

קלט: גרף לא מכוון $G=(V,E)$ ומספר $k\in\mathbb{N}$.

1. $\hat V\leftarrow V$, $\hat E\leftarrow\emptyset$.
2. לכל $e\in E$:
   • 2.1 צור קודקוד חדש $v_e$ (חדש, כלומר $v_e\notin V$ ושונה מכל קודקוד שנוצר קודם);
   • 2.2 הוסף את $v_e$ ל-$\hat V$;
   • 2.3 הוסף את $e\cup\{v_e\}$ ל-$\hat E$.
3. החזר את $H=(\hat V,\hat E)$ ואת אותו $k$.

הפלט הוא אינסטנס חוקי. לכל $e=\{x,y\}\in E$ מתקיים $x\ne y$ (הגרף פשוט) ו-$v_e\notin V$, ולכן $|e\cup\{v_e\}|=3$ בדיוק. כל איברי $\hat E$ הם תת-קבוצות של $\hat V$ בגודל $3$, כלומר $H$ הוא היפרגרף 3-אחיד. הפלט הוא זוג $\langle$היפרגרף 3-אחיד, מספר טבעי$\rangle$ — בדיוק סוג הקלט של $\mathrm{3H\text{-}VC}$. ([00:15:53]: "שימו לב שאנחנו צריכים להחזיר היפרגרף — 3-אחיד".)

ניתוח זמן ריצה

יהי $G=(V,E)$ ויהי $k\in\mathbb{N}$. שלב 1 לוקח זמן קבוע — הוא רק מסמן שמות ואינו מעתיק שום דבר. מספר האיטרציות בלולאה הוא בדיוק $|E|$, ובכל איטרציה מייצרים שם חדש, מוסיפים אותו לקבוצת קודקודים ומוסיפים קבוצה בת שלושה איברים לקבוצת ההיפר-קשתות — זמן קבוע (או $O(\log)$ בייצוג סביר של שמות). שלב 3 הוא כתיבת הפלט. סך הכול $O(|G|)$, פולינומי בגודל הקלט.

גם גודל הפלט פולינומי: $|\hat V|=|V|+|E|$ ו-$|\hat E|=|E|$. זה נחוץ — אחרת לא היה אפשר לכתוב את הפלט בזמן פולינומי מלכתחילה.

ניתוח נכונות, כיוון ראשון: $\langle G,k\rangle\in\mathrm{VC}\Rightarrow\langle H,k\rangle\in\mathrm{3H\text{-}VC}$

נניח $\langle G,k\rangle\in\mathrm{VC}$. אז קיימת $U\subseteq V$ כיסוי בקודקודים של $G$ עם $|U|\le k$.

נתבונן באותה $U$ בדיוק. שני דברים אנחנו מקבלים מיד, ואסור לדלג עליהם ([00:26:27]):

• $U\subseteq V\subseteq\hat V$, ולכן $U$ היא בכלל קבוצת קודקודים חוקית של $H$ — רק בזכות זה יש בכלל משמעות לשאלה אם היא כיסוי של $H$;
• $|U|\le k$ לא השתנה.

תהא $\hat e\in\hat E$ היפר-קשת. לפי בניית שלב 2, קיימת קשת $e\in E$ כך ש-$\hat e=e\cup\{v_e\}$ — זהו הקישור שלנו חזרה לגרף המקורי, ובלעדיו אין הוכחה ([00:28:39]: "אי אפשר להגיד 'נסמן' על משהו שאני לא יודע שהוא קיים"). מכיוון ש-$U$ כיסוי בקודקודים של $G$ ו-$e\in E$, מתקיים $e\cap U\ne\emptyset$. ומכיוון ש-$e\subseteq\hat e$, נובע $\hat e\cap U\;\supseteq\;e\cap U\;\ne\;\emptyset .$

מכיוון ש-$\hat e$ הייתה שרירותית, $U$ היא כיסוי קודקודים של $H$ בגודל $\le k$, ולכן $\langle H,k\rangle\in\mathrm{3H\text{-}VC}$. $\blacksquare$

ניתוח נכונות, כיוון שני: $\langle H,k\rangle\in\mathrm{3H\text{-}VC}\Rightarrow\langle G,k\rangle\in\mathrm{VC}$

נניח $\langle H,k\rangle\in\mathrm{3H\text{-}VC}$. אז קיימת $\hat U\subseteq\hat V$ כיסוי קודקודים של $H$ עם $|\hat U|\le k$.

כאן נופלת ההוכחה הנאיבית ([00:31:54]–[00:34:33]). אי אפשר לקחת את $\hat U$ כמות שהיא. $\hat U$ מוכלת ב-$\hat V$, ו-$\hat V$ מכילה קודקודים שאינם ב-$V$; ייתכן ש-$\hat U$ מכילה כאלה, ואז היא אינה תת-קבוצה של $V$ — ולשאלה "האם $\hat U$ כיסוי בקודקודים של $G$" אין אפילו משמעות. שימו לב לא-סימטריה מול הכיוון הראשון: שם קיבלנו קבוצה ב-$V$, וקבוצה ב-$V$ היא אוטומטית קבוצה ב-$\hat V$; כאן הכיוון הפוך והוא נשבר.

נבנה קבוצה $U\subseteq V$ באופן הבא:

לכל $v\in\hat U$:

• אם $v\in V$ — הכנס את $v$ ל-$U$;
• אחרת, מהבנייה קיימת קשת $xy\in E$ כך ש-$v=v_{xy}$ — הכנס את $x$ ל-$U$.

הערה על "$x$" ([00:47:21]–[00:49:30]). הקשת $xy$ היא קבוצה, ולכאורה אין בה "ראשון". אבל הקלט מגיע בסופו של דבר כמחרוזת, ובמחרוזת יש סדר; מה שלא מובטח לנו הוא איזה סדר. לכן "הקצה הראשון שמופיע בייצוג" הוא ביטוי חוקי לגמרי. בכל מקרה — הבחירה שרירותית והוכחה עוברת גם עם $y$.

הערה: אין צורך לנתח את זמן הריצה של הבנייה הזו ([00:36:39]). היא אינה חלק מהרדוקציה; היא חלק מההוכחה. התיאור הוא אלגוריתמי רק כדי לבטא את הקבוצה בנוחות.

מיד מתקבלים שני דברים. ראשית, $U\subseteq V$ מהבנייה — כל איבר שהוכנס הוא או $v\in V$ או קצה של קשת ב-$E$. שנית, $|U|\;\le\;|\hat U|\;\le\;k .$

למה רק $\le$ ולא $=$ ([00:39:16]–[00:40:20]). ההעתקה $\hat U\to U$ אינה בהכרח חד-חד-ערכית. אם למשל $xy$ ו-$xw$ הן שתי קשתות ב-$E$ ושני הקודקודים $v_{xy},v_{xw}$ שייכים ל-$\hat U$, שניהם מתורגמים ל-$x$ ונספרים פעם אחת. וכן ייתכן ש-$x$ עצמו כבר היה ב-$\hat U$ וגם $v_{xy}$ היה בה. אנחנו קיבלנו את $\hat U$ "מהשמיים" ואיננו רשאים להניח עליה מינימליות. אבל $\le k$ מספיק לנו לגמרי, כי בכיסוי בקודקודים תמיד אפשר להשלים כלפי מעלה.

נראה ש-$U$ כיסוי בקודקודים של $G$. תהא $e\in E$. אז קיימים $x,y\in V$ עם $e=\{x,y\}$, ומהבנייה $\{x,y,v_{xy}\}\in\hat E .$ מכיוון ש-$\hat U$ כיסוי קודקודים של $H$, מתקיים $\{x,y,v_{xy}\}\cap\hat U\;\ne\;\emptyset .$ נחלק לשני מקרים משלימים:

מקרה 1: $x\in\hat U$ או $y\in\hat U$. אז לפחות אחד מהם ב-$V$ ושייך ל-$\hat U$, ולכן לפי הכלל הראשון של הבנייה הוא הוכנס ל-$U$. כלומר $x\in U$ או $y\in U$, ולכן $e\cap U\ne\emptyset$.

מקרה 2: $x\notin\hat U$ וגם $y\notin\hat U$. מכיוון שהחיתוך אינו ריק, בהכרח $v_{xy}\in\hat U$. $v_{xy}\notin V$, ולכן לפי הכלל השני של הבנייה הוכנס $x$ ל-$U$. לכן $x\in U$ ומכאן שוב $e\cap U\ne\emptyset$.

בשני המקרים $e\cap U\ne\emptyset$. מכיוון ש-$e$ הייתה שרירותית, $U$ היא כיסוי בקודקודים של $G$ בגודל $\le k$, ולכן $\langle G,k\rangle\in\mathrm{VC}$. $\blacksquare$

מסקנה

$R$ היא רדוקציה בזמן פולינומי מ-$\mathrm{VC}$ ל-$\mathrm{3H\text{-}VC}$, כלומר $\mathrm{VC}\le_p\mathrm{3H\text{-}VC}$. מכיוון ש-$\mathrm{VC}$ היא NP-קשה (משפט 1, שיעור 10), גם $\mathrm{3H\text{-}VC}$ היא NP-קשה. $\blacksquare$

הערת כתיבה שהמרצה עצר עליה ([00:45:09]–[00:46:14]). המקרה השני נכתב בדיוק כשלילה של הראשון: "$x\notin\hat U$ וגם $y\notin\hat U$", ולא "נניח $v_{xy}\in\hat U$". שני הניסוחים נכונים כאן ואף אחד מהם אינו שגיאה — אבל כהרגל עבודה עדיף תמיד לחלק לשני מקרים משלימים ("עצים בינריים של מקרים"), כי אחרת קל לפספס מקרה שלישי שלא חשבתם עליו. זה עניין של הימנעות מטעויות, לא של סגנון.

תרגיל 4(ב): אלגוריתם קירוב ביחס $3$ לכיסוי המינימלי בהיפרגרף 3-אחיד

הניסוח (כפי שנמסר)

(ב) נסתכל על בעיית המינימיזציה שבה הקלט הוא היפרגרף 3-אחיד $H$ והמטרה היא למצוא כיסוי קודקודים ב-$H$ קטן ככל האפשר. הוכיחו כי קיים אלגוריתם עם זמן ריצה פולינומי לבעיה אשר משיג יחס קירוב $3$.

הרעיון

זהו בדיוק אלגוריתם ה-$2$-קירוב ל-$\mathrm{VC}$ משיעור 13 (משפט 1), עם $3$ במקום $2$. הרעיון שלו לא השתנה כהוא זה: אוספים היפר-קשתות זרות בזוגות, משלמים על כל אחת את כל שלושת קודקודיה, ומשתמשים בקבוצת ההיפר-קשתות שנאספו כחסם תחתון על האופטימום. המרצה אמר את זה במפורש ([00:52:49]): "ראינו אלגוריתם קירוב ביחס $2$ ל-$\mathrm{VC}$, אז כבר עשינו את רוב העבודה."

האלגוריתם

קלט: היפרגרף 3-אחיד $H=(V,E)$.

1. אתחל $C\leftarrow\emptyset$, $F\leftarrow\emptyset$.
2. כל עוד יש ב-$H$ היפר-קשת $e=\{x,y,z\}\in E$:
   • 2.1 הוסף ל-$C$ את $x,y,z$; הוסף ל-$F$ את $e$;
   • 2.2 מחק מ-$H$ את $x,y,z$ ואת כל ההיפר-קשתות המחוברות אליהן.
3. החזר את $C$.

הערה: $F$ היא "משתנה רפאים" ([00:53:50], [00:56:27]). האלגוריתם אינו זקוק ל-$F$ כדי לרוץ, והיא אינה משפיעה על הפלט. היא קיימת אך ורק לצורך הניתוח. המרצה ציין שברוב הספרים אין מסמנים אותה בתוך תיאור האלגוריתם אלא רק בהוכחה — שתי הדרכים תקינות.

הערה: למה מוחקים את הקודקודים ולא רק את ההיפר-קשתות ([00:57:33]). אפשר היה לכתוב "מחק את כל ההיפר-קשתות המחוברות ל-$x,y,z$" ולהשאיר קודקודים מבודדים; זה שקול לחלוטין. מחיקת הקודקודים נבחרה כי היא הופכת את הזרות בזוגות של $F$ לגלויה לעין, וזרות זו היא לב הניתוח.

(1) ניתוח זמן ריצה

יהי $H=(V,E)$ ונריץ עליו את האלגוריתם. שלב 1 לוקח זמן קבוע.

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

עלות איטרציה בודדת. מציאת היפר-קשת ומחיקת שלושה קודקודים וכל ההיפר-קשתות הנוגעות בהם דורשות מעבר על כל הקודקודים ועל כל ההיפר-קשתות — $O(|V|\cdot|E|)$ בחסם גס.

סך הכול $O(|H|^2)$, פולינומי בגודל הקלט. $\blacksquare$

הערה ([01:00:46]–[01:01:20]). אפשר לנתח הדוק בהרבה: כל היפר-קשת "נוגעים" בה לכל היותר פעם אחת לאורך כל הריצה, ולכן אפשר לסכום את העלויות לאורך האיטרציות במקום להכפיל. המרצה העדיף במכוון את החסם הגס: "כל מה שמעניין אותי זה שזה פולינומי." סטודנט גם הצביע על כך שהניתוח $O(|V|\cdot|E|)$ לאיטרציה הוא רופף כי אפשר לעבור רק על שכני $x,y,z$ — המרצה אישר שגם זה נכון וגם זה מספיק.

(2) פיזביליות

יהי $H=(V,E)$, ונסמן ב-$C$ את הפלט. ראשית, $C\subseteq V$ — כל מה שהוכנס ל-$C$ הוא קודקוד של היפר-קשת קיימת.

תהא $e\in E$ היפר-קשת של הקלט המקורי. האלגוריתם עוצר רק כאשר אין יותר היפר-קשתות ב-$H$, ולכן במהלך הריצה $e$ נמחקה. זו נקודת המוצא של כל הטיעון.

מתי נמחקת היפר-קשת? רק בשלב 2.2, וזה קורה בדיוק כאשר אחד מקודקודיה נמחק מהגרף. וקודקוד נמחק אך ורק בשלב 2.2, ובאותו רגע (שלב 2.1 של אותה איטרציה) הוא הוכנס ל-$C$. לכן קיים $u\in e$ עם $u\in C$, כלומר $e\cap C\;\ne\;\emptyset .$

מכיוון ש-$e$ הייתה שרירותית, $C$ היא כיסוי קודקודים של $H$, ובפרט פתרון אפשרי לבעיה. $\blacksquare$

הערה: אין צורך בחלוקה למקרים ([01:06:11]–[01:07:13]). בכיתה הוצע לחלק ל"או ש-$e$ היא זו שנבחרה, או שנמחקה בגלל שכנה". המרצה הראה שזה מיותר: בשני המקרים הסיבה למחיקה זהה — אחד מקודקודי $e$ נכנס ל-$C$. חלוקה למקרים שאינה נדרשת אינה שגיאה, אבל הטיעון האחיד קצר ובטוח יותר.

(3) יחס הקירוב

נסמן ב-$C_{\mathrm{opt}}$ כיסוי קודקודים מינימלי של $H$, וב-$F$ את קבוצת ההיפר-קשתות שהאלגוריתם צבר.

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

שלב ב: התאמה חד-חד-ערכית מ-$F$ ל-$C_{\mathrm{opt}}$. תהא $e\in F$. מכיוון ש-$F\subseteq E$ ומכיוון ש-$C_{\mathrm{opt}}$ הוא כיסוי קודקודים של $H$, מתקיים $e\cap C_{\mathrm{opt}}\ne\emptyset$, כלומר קיים $x\in C_{\mathrm{opt}}$ עם $x\in e$. נגדיר $\varphi:F\to C_{\mathrm{opt}},\qquad \varphi(e)=\text{some } x\in e\cap C_{\mathrm{opt}}$ (אם יש כמה — בוחרים אחד שרירותית). $\varphi$ מוגדרת היטב בדיוק בזכות היות $C_{\mathrm{opt}}$ כיסוי.

$\varphi$ חד-חד-ערכית: אם $e\ne\hat e$ ב-$F$, אז לפי שלב א הן זרות; $\varphi(e)\in e$ ו-$\varphi(\hat e)\in\hat e$, ולכן בהכרח $\varphi(e)\ne\varphi(\hat e)$.

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

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

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

מאיפה בא ה-$3$. בדיוק מ-$|C|=3|F|$, כלומר מכך שהיפר-קשת מכילה שלושה קודקודים ואנחנו משלמים על כולם. באותה הוכחה בדיוק, על היפרגרף $r$-אחיד, מתקבל יחס קירוב $r$; המקרה $r=2$ הוא ה-$2$-קירוב ל-$\mathrm{VC}$ משיעור 13.

הערה: מהות מול ערך ([01:07:46]–[01:09:23]). שאלה שעלתה: האם צריך להוכיח שהפלט הוא "פתרון" מעבר לכך שהוא כיסוי? התשובה של המרצה: בכל בעיית אופטימיזציה יש מהות (מה הופך אובייקט לפתרון אפשרי) ויש ערך (מה שממקסמים או ממזערים). מזהים את הערך בקלות — הוא הדבר שעליו עושים מקסימום/מינימום; כל השאר הוא מהות. כאן הערך הוא הגודל, והמהות היא "להיות כיסוי קודקודים". ב-$\mathrm{MAXCUT}$ הערך הוא גודל החתך והמהות היא רק "להיות קבוצת קודקודים", ולכן שם כל קבוצה פיזבילית — וזה בדיוק מקור הבלבול.

תרגיל 5: חתך מקסימלי בגרף מכוון — קירוב $\tfrac14$

הניסוח (כפי שנמסר)

עבור קבוצת קודקודים $U\subseteq V$ בגרף מכוון $G=(V,E)$, החתך המושרה על ידי $U$, שיסומן $\delta(U)$, הוא קבוצת כל הקשתות בגרף היוצאות מ-$U$, כלומר הזנב שלהן ב-$U$ והראש שלהן ב-$\bar U$. שימו לב שבניגוד לגרף לא מכוון, החתכים המושרים על ידי $U$ ו-$\bar U$ אינם בהכרח שווים. נגדיר בעיית מקסימיזציה באופן הבא:

קלט: גרף פשוט מכוון $G=(V,E)$. מטרה: למצוא בגרף $G$ קבוצת קודקודים $U\subseteq V$ עבורה הגודל של $\delta(U)$ מקסימלי.

הוכיחו כי קיים אלגוריתם עם זמן ריצה פולינומי לבעיה אשר משיג יחס קירוב $\tfrac14$.

הטעות שרוב הכיתה עשתה — ולמה היא טעות

[01:19:25]–[01:21:00]. הפתרון שהוגש על ידי הרוב המוחלט היה: "לכל קודקוד באופן בלתי תלוי, בהסתברות $\tfrac12$, נכניס אותו ל-$U$", ואז חישוב $\mathbb{E}[|\delta(U)|]=\tfrac14|E|$. זה אינו אלגוריתם קירוב. אלגוריתם קירוב חייב להבטיח את היחס בכל ריצה אפשרית; הניתוח ההסתברותי מבטיח אותו רק בתוחלת, והאלגוריתם אינו דטרמיניסטי. נכון שראינו איך לדה-רנדם ניתוח כזה בשיטת התוחלות המותנות (שיעור 20, משפט 7) — אבל אז צריך לכתוב את זה. המרצה הוסיף כלל אצבע: הדבר הראשון שבודקים במדעי המחשב הוא טיפוס; ודאו שמה שאתם מחזירים הוא מהטיפוס שהתבקשתם להחזיר.

החישוב עצמו, לצורך הבנת המספרים: קשת מכוונת $(u,v)$ שייכת ל-$\delta(U)$ אם ורק אם $u\in U$ וגם $v\notin U$, ובניסוי האחיד זה קורה בהסתברות $\tfrac12\cdot\tfrac12=\tfrac14$. לפי לינאריות התוחלת $\mathbb{E}[|\delta(U)|]=\tfrac14|E|$. זו טענה נכונה ומעניינת (השוו לשיעור 19, משפט 1, שם המקרה הלא מכוון נותן $\tfrac12|E|$) — היא פשוט אינה עונה על השאלה שנשאלה.

הצעה נוספת שנפסלה ([01:23:38]–[01:25:13]). סטודנט הציע גרסה חמדנית: להכניס כל קודקוד לצד שמגדיל את "החתך" הכי הרבה. בגרף מכוון יש עכשיו ארבעה סוגי קשתות ($U\to U$, $U\to\bar U$, $\bar U\to U$, $\bar U\to\bar U$), ולכן "החתך" אינו מוגדר היטב: איזה חתך מגדילים? יש שתי דרכים לתקן — או למקסם את סכום שני החתכים המכוונים, או להתעלם לגמרי מהכיוונים ולספור קשתות ללא כיוון. הכוונה של הסטודנט הייתה נכונה, אבל המרצה עמד על כך שבכתיבה חייבים לומר איזו: "אני לא חי אצלכם בראש."

האלגוריתם

קלט: גרף מכוון $G=(V,E)$.

1. נסמן ב-$\hat G=(V,\hat E)$ את הגרף הלא מכוון המתקבל מ-$G$ על ידי מחיקת כיווני הקשתות (שומרים כל קשת בנפרד — ראו ההערה מיד).
2. נריץ את אלגוריתם הקירוב ביחס $\tfrac12$ שראינו בשיעור לבעיית $\mathrm{MAXCUT}$ על $\hat G$; נסמן ב-$U$ את פלט האלגוריתם.
3. אם $|\delta(U)|\ge|\delta(\bar U)|$ ב-$G$ — החזר את $U$; אחרת — החזר את $\bar U$.

הערה קריטית: $\hat G$ הוא מולטיגרף ([01:27:23]). $G$ פשוט מכוון, ולכן ייתכן שגם $(u,v)\in E$ וגם $(v,u)\in E$. אחרי מחיקת הכיוונים אלה שתי קשתות מקבילות בין $u$ ל-$v$, ואנחנו שומרים את שתיהן. זה אינו פרט טכני: אנחנו זקוקים לכך ש-$|\hat E|=|E|$ בדיוק. אילו היינו ממזגים קשתות מקבילות, ההבטחה $|(U,\bar U)|\ge\tfrac12|\hat E|$ הייתה מדברת על מספר קטן יותר, והחסם הסופי $\tfrac14|E|$ היה נשבר. לפי משפט 3 לעיל, אלגוריתם ה-$\tfrac12$-קירוב אכן עובד על מולטיגרפים.

(1) ניתוח זמן ריצה

שלב 1 הוא מעבר יחיד על $E$ שבו מוחקים את הכיוון מכל קשת: $O(|E|)$.

שלב 2 רץ בזמן פולינומי בגודל $\hat G$, כי אלגוריתם הקירוב שראינו בשיעור הוא פולינומי (שיעור 13, משפט 3 — $O(|G|^2)$). מכיוון ש-$|\hat G|=O(|G|)$, זהו זמן פולינומי ב-$|G|$.

שלב 3 דורש חישוב של $|\delta(U)|$ ושל $|\delta(\bar U)|$: מעבר יחיד על $E$ שבו לכל קשת $(u,v)$ בודקים לאיזה צד שייכים $u$ ו-$v$ ומגדילים את המונה המתאים — $O(|E|)$, ליניארי.

סך הכול פולינומי בגודל הקלט. $\blacksquare$

[01:38:51]: את חשבון שלב 3 סטודנט הוא שהעיר שחסר, והמרצה אישר: "אתה צודק, צריך להוסיף את זה — להגיד שזה קורה בזמן ליניארי." הסיכום הכתוב מדלג על השלב הזה; כאן הוא נכתב במפורש.

(2) פיזביליות

הפלט הוא $U$ או $\bar U$, ושתיהן תת-קבוצות של $V$. מכיוון שכל תת-קבוצה של $V$ היא פתרון אפשרי לבעיה (הגדרה 3), הפלט אפשרי תמיד. $\blacksquare$

שימו לב שקבוצת הקודקודים לא השתנתה בשלב 1 — $\hat G$ מוגדר על אותה $V$ — ולכן הפלט של אלגוריתם ה-$\mathrm{MAXCUT}$ הוא קבוצת קודקודים חוקית גם ב-$G$, ואפשר לחזור איתה לגרף המכוון ([01:27:57]).

(3) יחס הקירוב

יהי $G=(V,E)$ גרף מכוון, ויהי $\hat G=(V,\hat E)$ הגרף הלא מכוון (המולטיגרף) המתקבל ממנו במחיקת הכיוונים, כך ש-$|\hat E|=|E|$.

נסמן ב-$U$ את פלט אלגוריתם ה-$\mathrm{MAXCUT}$ על $\hat G$, וב-$(U,\bar U)$ את החתך המושרה על ידי $U$ ב-$\hat G$ (כלומר, כל הקשתות הלא מכוונות שקצה אחד שלהן ב-$U$ והשני ב-$\bar U$). נסמן ב-$\delta(U),\delta(\bar U)$ את שני החתכים המכוונים ב-$G$.

שלב א — ההבטחה של אלגוריתם ה-$\mathrm{MAXCUT}$. לפי משפט 3, $|(U,\bar U)|\;\ge\;\tfrac12|\hat E|\;=\;\tfrac12|E| .$

שלב ב — הזהות המרכזית. תהי $\hat e\in(U,\bar U)$ קשת בחתך הלא מכוון, ותהי $(u,v)\in E$ הקשת המכוונת שממנה היא נוצרה. שני קצותיה נמצאים בצדדים מנוגדים, ולכן בדיוק אחת משתי האפשרויות מתקיימת: או ש-$u\in U$ ו-$v\in\bar U$, ואז $(u,v)\in\delta(U)$; או ש-$u\in\bar U$ ו-$v\in U$, ואז $(u,v)\in\delta(\bar U)$. ולהפך, כל קשת ב-$\delta(U)$ או ב-$\delta(\bar U)$ מניבה קשת בחתך הלא מכוון. שתי הקבוצות $\delta(U),\delta(\bar U)$ זרות. לכן $|\delta(U)|+|\delta(\bar U)|\;=\;|(U,\bar U)| .$