מפת הסיבוכיות
EN
ניפוח כל קשת לגודל 3

VC ≤p 3H-VC

VC≤p3H-VC\mathrm{VC}\le_p\mathrm{3H\text{-}VC}, ולכן כיסוי קודקודים בהיפרגרף 3-אחיד הוא NP-קשה. היפרגרף 3-אחיד הוא זוג H=(V,E)H=(V,E) שבו כל היפר-קשת היא תת-קבוצה של VV בגודל 33.

הבנייה

למה דווקא מ-VC\mathrm{VC}. היא ה"בעיה הקרובה": ההגדרה של כיסוי קודקודים בהיפרגרף היא מילה במילה ההגדרה מ-VC\mathrm{VC} (גרף רגיל הוא היפרגרף 2-אחיד). הניחוש הראשון תמיד הבעיה הדומה ביותר. הקושי הטכני היחיד: הפלט חייב להיות 3-אחיד, וקשתות גרף הן בגודל 22 — צריך "לנפח" כל קשת לגודל 33 בלי לשנות את התשובה.

האלגוריתם RR. על קלט G=(V,E)G=(V,E) ו-k∈Nk\in\mathbb N:

  1. V^←V\hat V\leftarrow V, E^←∅\hat E\leftarrow\emptyset.
  2. לכל e∈Ee\in E:
    • צור קודקוד חדש vev_e (חדש: ve∉Vv_e\notin V ושונה מכל קודקוד שנוצר קודם);
    • הוסף את vev_e ל-V^\hat V;
    • הוסף את e∪{ve}e\cup\{v_e\} ל-E^\hat E.
  3. החזר את H=(V^,E^)H=(\hat V,\hat E) ואת אותו kk.

הפלט הוא אינסטנס חוקי. לכל e={x,y}∈Ee=\{x,y\}\in E מתקיים x≠yx\ne y (הגרף פשוט) ו-ve∉Vv_e\notin V, ולכן ∣e∪{ve}∣=3|e\cup\{v_e\}|=3 בדיוק; כל איברי E^\hat E הם תת-קבוצות של V^\hat V בגודל 33.

המחשה

בנייה מודרכת

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

שלב 1 מתוך 7
⟨G, k = 2⟩ ∈ VC ?
כיסוי קודקודים לכיסוי בהיפרגרף 3-אחיד: כל קשת מנופחת בעזרת קודקוד חדשגרף המקור G עם הקודקודים a, b, c, d והקשתות ab, ac, bc, cd מופיע בצד אחד. בצד השני ההיפרגרף H שומר את ארבעת הקודקודים, מוסיף קודקוד ריבועי לכל קשת, ומצייר כל היפר־קשת כשטח מוצלל שמכסה בדיוק שלושה קודקודים. ההדגשות מראות את הכיסוי U שנשאר ללא שינוי, כיסוי של ההיפרגרף שמכיל קודקוד חדש, ואת מפת התיקון שמחליפה אותו באחד משני קצותיו האמיתיים.G — גרף המקור (קשתות בגודל 2)abacbccdabcd
קודקוד מקורי מתוך V (עיגול)

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

VC ∈ ⟹ 3H-VC ∈

נניח ⟨G,k⟩∈VC\langle G,k\rangle\in\mathrm{VC}; אז קיימת U⊆VU\subseteq V כיסוי בקודקודים של GG עם ∣U∣≤k|U|\le k.

נתבונן באותה UU בדיוק. שני דברים מתקבלים מיד ואסור לדלג עליהם: U⊆V⊆V^U\subseteq V\subseteq\hat V, ולכן UU היא בכלל קבוצת קודקודים חוקית של HH — רק בזכות זה יש משמעות לשאלה אם היא כיסוי של HH; וכן ∣U∣≤k|U|\le k לא השתנה.

תהא e^∈E^\hat e\in\hat E היפר-קשת. לפי בניית שלב 2 קיימת קשת e∈Ee\in E כך ש-e^=e∪{ve}\hat e=e\cup\{v_e\} — זהו הקישור חזרה לגרף המקורי, ובלעדיו אין הוכחה. מכיוון ש-UU כיסוי של GG ו-e∈Ee\in E, מתקיים e∩U≠∅e\cap U\ne\emptyset; ומכיוון ש-e⊆e^e\subseteq\hat e, e^∩U  ⊇  e∩U  ≠  ∅.\hat e\cap U\;\supseteq\;e\cap U\;\ne\;\emptyset .

מכיוון ש-e^\hat e שרירותית, UU כיסוי קודקודים של HH בגודל ≤k\le k, ולכן ⟨H,k⟩∈3H-VC\langle H,k\rangle\in\mathrm{3H\text{-}VC}.

3H-VC ∈ ⟹ VC ∈

נניח ⟨H,k⟩∈3H-VC\langle H,k\rangle\in\mathrm{3H\text{-}VC}; אז קיימת U^⊆V^\hat U\subseteq\hat V כיסוי של HH עם ∣U^∣≤k|\hat U|\le k.

כאן נופלת ההוכחה הנאיבית. אי אפשר לקחת את U^\hat U כמות שהיא: היא מוכלת ב-V^\hat V, ו-V^\hat V מכילה קודקודים שאינם ב-VV; ייתכן ש-U^\hat U מכילה כאלה, ואז היא אינה תת-קבוצה של VV ולשאלה "האם היא כיסוי של GG" אין אפילו משמעות. שימו לב לאי-סימטריה מול הכיוון הראשון: שם קיבלנו קבוצה ב-VV, וקבוצה ב-VV היא אוטומטית קבוצה ב-V^\hat V; כאן הכיוון הפוך והוא נשבר.

נבנה U⊆VU\subseteq V: לכל v∈U^v\in\hat U — אם v∈Vv\in V נכניס את vv ל-UU; אחרת מהבנייה קיימת קשת xy∈Exy\in E עם v=vxyv=v_{xy}, ונכניס את xx ל-UU.

(הבנייה הזאת אינה חלק מהרדוקציה — היא חלק מההוכחה, ולכן אין צורך לנתח את זמן הריצה שלה.)

מיד: U⊆VU\subseteq V מהבנייה, וכן ∣U∣≤∣U^∣≤k|U|\le|\hat U|\le k. רק ≤\le ולא ==, כי ההעתקה U^→U\hat U\to U אינה בהכרח חד-חד-ערכית: אם vxy,vxw∈U^v_{xy},v_{xw}\in\hat U שניהם מתורגמים ל-xx. קיבלנו את U^\hat U "מהשמיים" ואיננו רשאים להניח עליה מינימליות — אבל ≤k\le k מספיק, כי בכיסוי תמיד אפשר להשלים כלפי מעלה.

UU כיסוי של GG: תהא e∈Ee\in E; קיימים x,y∈Vx,y\in V עם e={x,y}e=\{x,y\}, ומהבנייה {x,y,vxy}∈E^\{x,y,v_{xy}\}\in\hat E. מכיוון ש-U^\hat U כיסוי של HH, מתקיים {x,y,vxy}∩U^≠∅\{x,y,v_{xy}\}\cap\hat U\ne\emptyset. נחלק לשני מקרים משלימים:

מקרה 1: x∈U^x\in\hat U או y∈U^y\in\hat U. אז לפחות אחד מהם ב-VV ושייך ל-U^\hat U, ולכן לפי הכלל הראשון הוכנס ל-UU; מכאן e∩U≠∅e\cap U\ne\emptyset.

מקרה 2: x∉U^x\notin\hat U וגם y∉U^y\notin\hat U. מכיוון שהחיתוך אינו ריק, בהכרח vxy∈U^v_{xy}\in\hat U; ומכיוון ש-vxy∉Vv_{xy}\notin V, לפי הכלל השני הוכנס xx ל-UU. מכאן שוב e∩U≠∅e\cap U\ne\emptyset.

בשני המקרים e∩U≠∅e\cap U\ne\emptyset, ולכן UU כיסוי של GG בגודל ≤k\le k, כלומר ⟨G,k⟩∈VC\langle G,k\rangle\in\mathrm{VC}.

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

זמןO(|G|)
מקוםO(|G|)
גודל הפלט|V̂| = |V| + |E|, |Ê| = |E|

מספר האיטרציות הוא בדיוק ∣E∣|E|, ובכל אחת מייצרים שם חדש ומוסיפים קבוצה בת שלושה איברים — זמן קבוע (או O(log⁡)O(\log) בייצוג סביר של שמות). גם גודל הפלט פולינומי: ∣V^∣=∣V∣+∣E∣|\hat V|=|V|+|E| ו-∣E^∣=∣E∣|\hat E|=|E|. זה נחוץ — אחרת לא היה אפשר לכתוב את הפלט בזמן פולינומי מלכתחילה.

מה זה קונה

3H-VC\mathrm{3H\text{-}VC} היא NP-קשה. גרסת המינימיזציה שלה מקבלת אלגוריתם קירוב ביחס 33 — הכללה ישירה של אלגוריתם ה-22-קירוב ל-VC\mathrm{VC}, כשהמספר 33 מגיע מגודל ההיפר-קשת.

מלכודות

  • אי-סימטריה בין הכיוונים. בכיוון הראשון "אותה UU" עובד, כי V⊆V^V\subseteq\hat V. בכיוון השני זה נשבר לגמרי, כי V^⊈V\hat V\not\subseteq V. זו התבנית החוזרת בכל רדוקציה שמוסיפה קודקודים — ואותה בדיוק ראינו ב-VC≤pDS\mathrm{VC}\le_p\mathrm{DS}.

  • "נסמן" דורש קיום. אי אפשר לומר "נסמן ב-ee את הקשת ש-e^\hat e בא ממנה" בלי לומר קודם שהיא קיימת לפי הבנייה. זה מה שמקשר את הפלט חזרה לקלט.

  • עדיף לחלק לשני מקרים משלימים. המקרה השני נכתב בדיוק כשלילת הראשון ולא כ"נניח vxy∈U^v_{xy}\in\hat U" — שני הניסוחים נכונים כאן, אבל חלוקה משלימה מונעת פספוס של מקרה שלישי שלא חשבתם עליו.

השרשרת

נשענת על

מאיפה זה נקרא

  • שיעור 25תרגיל 4(א): 3H-VC\mathrm{3H\text{-}VC} היא NP-קשה
  • תרגיל בקטלוגhypergraph-vc-np-hard