IS ≤p VC | Complexity Atlas

הבנייה

על קלט $\langle G,k\rangle$ עם $G=(V,E)$ :

החזר $\langle G,\ |V|-k\rangle$ .

זהו. אותו גרף בדיוק, רק המספר משתנה.

הבנייה נשענת על הבחנה אחת, שהיא הלב של השיעור: לכל $U\subseteq V$ , $U \text{ כיסוי בקודקודים של } G \iff V\setminus U \text{ בלתי תלויה ב-} G .$ שתי הטענות אומרות בדיוק את אותו דבר על כל קשת: "לכל קשת יש קצה ב- $U$ " שקול ל"אין קשת ששני קצותיה מחוץ ל- $U$ ".

המחשה

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

IS ∈ ⟹ VC ∈

נניח $\langle G,k\rangle\in\mathrm{IS}$ . אזי קיימת $U\subseteq V$ בלתי תלויה ב- $G$ עם $|U|=k$ . לפי ההבחנה, $V\setminus U$ היא כיסוי בקודקודים של $G$ , וגודלה $|V\setminus U|=|V|-|U|=|V|-k .$ לכן קיים ב- $G$ כיסוי בקודקודים בגודל $|V|-k$ , ומכאן $\langle G,|V|-k\rangle\in\mathrm{VC}$ .

VC ∈ ⟹ IS ∈

נניח $\langle G,|V|-k\rangle\in\mathrm{VC}$ . אזי קיים כיסוי בקודקודים $U\subseteq V$ של $G$ עם $|U|=|V|-k$ . לפי ההבחנה, $V\setminus U$ בלתי תלויה ב- $G$ , וגודלה $|V\setminus U|=|V|-(|V|-k)=k .$ לכן $\langle G,k\rangle\in\mathrm{IS}$ .

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

זמןO(|⟨G,k⟩|²)

מקוםO(|⟨G,k⟩|)

גודל הפלט|⟨G,k⟩| + O(1)

האלגוריתם מעתיק את הקלט ומבצע חיסור יחיד. במודל RAM זה אפילו זמן קבוע; במכונת טיורינג יש לבצע חיסור בינארי על מספר שאורכו לכל היותר אורך הקלט, כלומר $O(|\langle G,k\rangle|^2)$ בגישה נאיבית. בכל מקרה פולינומי, וזה כל מה שנדרש.

מה זה קונה

$\mathrm{VC}$ היא NP-קשה, ומכיוון שהיא גם ב- $\mathrm{NP}$ (העד הוא $U$ ; המאמת בודק $|U|\le k$ ועובר על הקשתות) — היא NP-שלמה. משם היא הופכת לנקודת המוצא של $\mathrm{VC}\le_p\mathrm{SUBSET\text{-}SUM}$ , $\mathrm{VC}\le_p\mathrm{DS}$ ו- $\mathrm{VC}\le_p\mathrm{3H\text{-}VC}$ .

מלכודות

"בדיוק $k$ " מול "לפחות/לכל היותר $k$ ". ההוכחה משתמשת בגודל בדיוק $k$ ובגודל בדיוק $|V|-k$ , בעוד ההגדרות אומרות "לפחות $k$ " ב- $\mathrm{IS}$ ו"לכל היותר $k$ " ב- $\mathrm{VC}$ . זה חוקי: לכיסוי אפשר תמיד להוסיף קודקודים (הוספה אינה מקלקלת כיסוי), ומקבוצה בלתי תלויה אפשר תמיד להוציא (תת-קבוצה של בלתי תלויה היא בלתי תלויה). שימו לב שהכיווניות הפוכה בין שתי הבעיות — ובכל בעיה חדשה יש לשאול מחדש אם השקילות הזאת מתקיימת.
"למה לא הזהות?" — שתי סיבות. הכיוון: אנחנו רוצים רדוקציה אל $\mathrm{VC}$ , לא ממנה, כי המטרה היא להוכיח ש- $\mathrm{VC}$ קשה. והמספר: הגרף אכן נשאר אותו גרף, אבל $k$ חייב להשתנות, בדיוק בגלל הקשר בין גודל קבוצה לגודל המשלים שלה.

השרשרת

נשענת על

3SAT ≤p IS

משמשת בהמשך ל

מאיפה זה נקרא

שיעור 10משפט 2: $\mathrm{IS} \le_p \mathrm{VC}$ , ולכן $\mathrm{VC}$ היא NP-שלמה
תרגיל מודרךindependent-set-to-vertex-cover
2026 '2 מועד 2יחסי $\le_p$ בין גרסאות "בדיוק", "לפחות" ו"מינימלי" של כיסוי בקודקודים.