מפת הסיבוכיות
EN
שתילת $k-1$ קודקודים המחוברים לכל הישנים

co-IS ≤p MaxIS

IS‾≤pMaxIS\overline{\mathrm{IS}}\le_p\mathrm{MaxIS}, ולכן MaxIS\mathrm{MaxIS} היא coNP-קשה.

הבנייה

למת המשלימים (משיעור 21). תהי ff פונקציה הניתנת לחישוב בזמן פולינומי. אז ff היא רדוקציה מ-AA ל-BB אם ורק אם היא רדוקציה מ-A‾\overline A ל-B‾\overline B — שכן x∈A  ⟺  f(x)∈Bx\in A\iff f(x)\in B שקול לוגית ל-x∉A  ⟺  f(x)∉Bx\notin A\iff f(x)\notin B. זה מה שמאפשר לצאת מ-IS‾\overline{\mathrm{IS}}.

הרדוקציה. על קלט ⟨G,k⟩\langle G,k\rangle עם G=(V,E)G=(V,E):

  1. הוסף ל-GG עוד k−1k-1 קודקודים חדשים; נסמן V^=V∪(החדשים)\hat V=V\cup(\text{החדשים}), כך ש-∣V^∖V∣=k−1|\hat V\setminus V|=k-1.
  2. הוסף קשתות מכל קודקוד חדש אל כל אחד מקודקודי VV. בין הקודקודים החדשים לבין עצמם אין קשתות, ובין קודקודי VV לבין עצמם לא הוספנו ולא הסרנו דבר.
  3. החזר ⟨G^,k−1⟩\langle\hat G,k-1\rangle.

האינטואיציה. רוצים ש"אין ב-GG קבוצה בלתי תלויה בגודל kk" יתורגם לשאלת מקסימום. אם אין כזו, אז המקסימום ב-GG הוא לכל היותר k−1k-1 — אבל אין ערובה שהוא בדיוק k−1k-1. לכן "שותלים" קבוצה בלתי תלויה בגודל k−1k-1 בדיוק. קודקודים מבודדים לא היו עובדים: הם היו מצטרפים לקבוצות הישנות ומגדילים את המקסימום. חיבורם לכל הקודקודים הישנים גורם לקבוצה החדשה להתקיים בלי להתערבב.

המחשה

בנייה מודרכת

משלים IS → MaxIS

שלב 1 מתוך 7
⟨G, k⟩ = ⟨C₅, 4⟩משלים IS: האם אין ב־G קבוצה בלתי תלויה בגודל 4?
למת המשלימיםf רדוקציה מ־A ל־B ⇔ f רדוקציה מ־Ā ל־B̄ — ולכן מותר לצאת ממשלים IS.
מעגל באורך חמש ושלושה קודקודים שתולים המחוברים לכל קודקוד מקוריגרף המקור הוא מחומש בן חמישה קודקודים. שלושה קודקודים שתולים ניצבים בטור מימינו, בלי קשתות ביניהם ועם קשת דקה אל כל אחד מחמשת הקודקודים המקוריים. בשלב ההשוואה מוצג אותו גרף פעמיים, פעם עם קשתות החיבור ופעם בלעדיהן.G = C₅ — גרף הקלטv₁v₂v₃v₄v₅α(G) = 2 ≤ k − 1 = 3, אך לא בהכרח שווה
קודקוד מקורי של Vמלא: קשת מקורית של Gהקבוצה הבלתי תלויה הנדונה, מוקפת ב־✓

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

co-IS ∈ ⟹ MaxIS ∈

נניח ⟨G,k⟩∈IS‾\langle G,k\rangle\in\overline{\mathrm{IS}} — כלומר אין ב-GG קבוצה בלתי תלויה בגודל kk. צריך להוכיח את שני חלקי ה"וגם" של MaxIS\mathrm{MaxIS}:

(א) חלק הקיום. הקבוצה V^∖V\hat V\setminus V (הקודקודים החדשים) בלתי תלויה ב-G^\hat G: לא הוספנו שום קשת בין שני קודקודים חדשים. גודלה בדיוק k−1k-1. ✓

(ב) חלק ה"לכל". תהא U⊆V^U\subseteq\hat V בלתי תלויה ב-G^\hat G. ב-G^\hat G יש קשת בין כל קודקוד חדש ובין כל קודקוד ישן, ולכן UU אינה יכולה להכיל בו-זמנית חדש וישן; מכאן ש-U⊆V^∖VU\subseteq\hat V\setminus V או U⊆VU\subseteq V.

  • אם U⊆V^∖VU\subseteq\hat V\setminus V: אז ∣U∣≤k−1|U|\le k-1.
  • אחרת U⊆VU\subseteq V: מכיוון שלא הוספנו ולא הסרנו קשתות בין קודקודי VV, קבוצה בלתי תלויה ב-G^\hat G המוכלת ב-VV בלתי תלויה גם ב-GG. מכיוון שאין ב-GG בלתי תלויה בגודל kk, ולפי התורשתיות גם אין בגודל גדול מ-kk (אחרת היינו מורידים קודקודים ומקבלים בגודל kk בדיוק), נובע ∣U∣≤k−1|U|\le k-1.

בשני המקרים ∣U∣≤k−1|U|\le k-1. ✓

משני החלקים: המקסימום ב-G^\hat G הוא בדיוק k−1k-1, כלומר ⟨G^,k−1⟩∈MaxIS\langle\hat G,k-1\rangle\in\mathrm{MaxIS}.

MaxIS ∈ ⟹ co-IS ∈

נניח ⟨G^,k−1⟩∈MaxIS\langle\hat G,k-1\rangle\in\mathrm{MaxIS}. צריך להוכיח ⟨G,k⟩∈IS‾\langle G,k\rangle\in\overline{\mathrm{IS}}, כלומר: לכל קבוצה בלתי תלויה UU ב-GG מתקיים ∣U∣≠k|U|\ne k. זו טענת "לכל", ולכן פותחים ב"תהא".

תהא U⊆VU\subseteq V בלתי תלויה ב-GG.

  1. הרדוקציה לא הוסיפה שום קשת בין קודקודי VV — הקשתות היחידות שהוספנו יוצאות מהקודקודים החדשים. לכן UU, כתת-קבוצה של V^\hat V, בלתי תלויה גם ב-G^\hat G.
  2. מההנחה α(G^)=k−1\alpha(\hat G)=k-1, ולכן כל קבוצה בלתי תלויה ב-G^\hat G היא בגודל ≤k−1\le k-1. בפרט ∣U∣≤k−1|U|\le k-1.
  3. מכאן בפרט ∣U∣≠k|U|\ne k.

מכיוון שזה נכון לכל UU בלתי תלויה ב-GG, אין ב-GG קבוצה בלתי תלויה בגודל kk, כלומר ⟨G,k⟩∈IS‾\langle G,k\rangle\in\overline{\mathrm{IS}}.

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

זמןO(|⟨G,k⟩|²)
מקוםO(|V|²)
גודל הפלט|V| + k − 1 vertices, |E| + (k−1)|V| edges

הבחנה עדינה: בגודל הייצוג של הקלט המספר kk תופס רק log⁡k\log k ביטים, ולכן אסור לחסום שום דבר "באמצעות kk". אבל מותר להניח בלי הגבלת הכלליות k≤∣V∣k\le|V| — אם k>∣V∣k>|V| אז בוודאי אין ב-GG קבוצה בלתי תלויה בגודל kk (אין בו כלל kk קודקודים), והרדוקציה מחזירה במקרה זה מחרוזת קבועה ששייכת ל-MaxIS\mathrm{MaxIS}. לכן k−1<∣V∣k-1<|V|, הוספת הקודקודים היא O(∣V∣)O(|V|), והוספת הקשתות היא (k−1)⋅∣V∣=O(∣V∣2)(k-1)\cdot|V|=O(|V|^2).

שימו לב: כל קודקוד חדש מקבל קשת לכל קודקוד ישן, כלומר ∣V∣|V| קשתות — לא kk קשתות.

מה זה קונה

MaxIS\mathrm{MaxIS} היא coNP-קשה. יחד עם SAT≤pMaxIS\mathrm{SAT}\le_p\mathrm{MaxIS} היא גם NP-קשה, ושתי התכונות יחד יוצרות את המצב שבו MaxIS∈NP∪coNP\mathrm{MaxIS}\in\mathrm{NP}\cup\mathrm{coNP} אם ורק אם NP=coNP\mathrm{NP}=\mathrm{coNP}.

מלכודות

  • קודקודים מבודדים אינם עובדים. ההצעה "נוסיף k−1k-1 קודקודים מבודדים" כמעט נכונה — אבל קודקודים מבודדים מצטרפים לכל קבוצה בלתי תלויה קיימת ומגדילים את המקסימום ב-k−1k-1, ולכן חלק ה"לכל" נשבר.

  • מ"אין קבוצה בגודל kk" נובע "אין בגודל >k>k" — דרך התורשתיות: מקבוצה בלתי תלויה בגודל k+1k+1 אפשר להוריד קודקוד ולקבל אחת בגודל kk. זה טיעון של ההוכחה, לא של האלגוריתם: האלגוריתם אינו נוגע בקבוצות הבלתי תלויות כלל, הוא מטפל בגרף בלבד.

  • k=0k=0 צריך טיפול נפרד. לכל גרף ⟨G,0⟩∈IS\langle G,0\rangle\in\mathrm{IS} (הקבוצה הריקה), ולכן ⟨G,0⟩∉IS‾\langle G,0\rangle\notin\overline{\mathrm{IS}}; על קלט כזה הרדוקציה מחזירה מחרוזת קבועה שאיננה ב-MaxIS\mathrm{MaxIS}.

השרשרת

נשענת על

מאיפה זה נקרא

  • שיעור 22משפט 3: IS‾≤pMaxIS\overline{\mathrm{IS}}\le_p\mathrm{MaxIS}, ולכן MaxIS\mathrm{MaxIS} היא coNP-קשה

  • הטיפול במקרה k=0k=0 אינו מופיע באף אחד ממקורות השיעור — הוא השלמה שנכתבה בקובץ השיעור עצמו כדי שהבנייה תהיה מוגדרת על כל קלט.