VC ≤p DS | Complexity Atlas

הבנייה

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

לכל קשת $xy\in E$ : הוסף קודקוד חדש $v_{xy}$ וחבר אותו בקשת ל- $x$ ובקשת ל- $y$ .
הסר מהגרף המתקבל את כל הקודקודים המבודדים, והחזר את הגרף $\hat G=(\hat V,\hat E)$ יחד עם אותו $k$ .

מה עושה $v_{xy}$ , בשורה אחת: הוא כופה על אחד מבין $x,y$ להיות בפנים. זו כל הרדוקציה — תרגום הדרישה "כל קשת נגועה" לדרישה "כל קודקוד נשלט", על ידי הפיכת כל קשת לקודקוד שדורש שליטה.

למה צריך את שלב 2. קודקוד מבודד ב- $G$ אינו נוגע באף קשת ולכן לעולם אינו דרוש לכיסוי; לעומת זאת בקבוצה שולטת קודקוד מבודד חייב להיכנס לקבוצה, כי אין לו שכן שיכסה אותו. בלי שלב 2 היינו מחייבים את $\mathrm{DS}$ להוסיף קודקודים שאין להם מקבילה בצד $\mathrm{VC}$ , וזה היה מקלקל את שמירת התשובה. מכיוון שהסרת קודקודים מבודדים אינה משנה את התשובה של $\mathrm{VC}$ (הקשתות לא השתנו), מותר להניח מכאן ואילך ש- $G$ נטול קודקודים מבודדים.

התכונה המבנית שנשתמש בה שוב ושוב: לכל קודקוד חדש $v_{xy}$ יש בדיוק שני שכנים ב- $\hat G$ , והם $x$ ו- $y$ , ושניהם ב- $V$ .

המחשה

⟨G, k = 2⟩ ∈ VC ?

קודקוד מקורי מתוך V

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

VC ∈ ⟹ DS ∈

נניח $\langle G,k\rangle\in\mathrm{VC}$ . אז קיימת $U\subseteq V$ עם $\forall e\in E:\ e\cap U\ne\emptyset$ ו- $|U|\le k$ .

נתבונן באותה $U$ בדיוק, כתת-קבוצה של $\hat V$ (חוקי, כי $V\subseteq\hat V$ ). נראה שהיא שולטת ב- $\hat G$ . יהי $x\in\hat V$ ונניח $x\notin U$ (אם $x\in U$ אין מה להוכיח).

מקרה 1: $x\in V$ . מכיוון ש- $G$ נטול קודקודים מבודדים, קיים $y\in V$ עם $xy\in E$ . $U$ כיסוי, ולכן $x\in U$ או $y\in U$ ; הנחנו $x\notin U$ , ולכן $y\in U$ . וכן $xy\in E\subseteq\hat E$ . אז ל- $x$ יש שכן ב- $U$ .

מקרה 2: $x\notin V$ . אז $x$ נוצר בשלב 1, כלומר קיימים $a,b\in V$ עם $ab\in E$ ו- $x=v_{ab}$ . $U$ כיסוי, ולכן $a\in U$ או $b\in U$ ; ומהבנייה $ax\in\hat E$ וגם $bx\in\hat E$ . לכן קיים $y\in\{a,b\}\cap U$ עם $xy\in\hat E$ — ל- $x$ יש שכן ב- $U$ .

בשני המקרים $x\in U$ או שיש לו שכן ב- $U$ ; לכן $U$ שולטת ב- $\hat G$ , וגודלה $|U|\le k$ לא השתנה. מכאן $\langle\hat G,k\rangle\in\mathrm{DS}$ .

DS ∈ ⟹ VC ∈

נניח שקיימת $\hat U\subseteq\hat V$ שולטת ב- $\hat G$ עם $|\hat U|\le k$ .

כאן אי אפשר לקחת את $\hat U$ כמו שהיא — היא אולי מכילה קודקודים חדשים, ולכן אינה מוכלת ב- $V$ ובוודאי אינה כיסוי של $G$ . נבנה ממנה $U\subseteq V$ :

> לכל $x\in\hat U$ : אם $x\in V$ — נכניס את $x$ ל- $U$ ; אם $x\notin V$ — נכניס אחד משכניו (לפי כלל שרירותי קבוע; הבחירה אינה משנה).

$U\subseteq V$ : לכל $x\in\hat U\setminus V$ שני שכניו ב- $V$ , ובמקרה הראשון הכנסנו $x\in V$ עצמו.

גודל: לכל איבר של $\hat U$ הכנסנו לכל היותר איבר אחד, ולכן $|U|\le|\hat U|\le k$ . (ייתכן שהכנסנו את אותו קודקוד פעמיים ואז $|U|$ קטן ממש — רק לטובתנו, כי דרוש חסם עליון.)

$U$ כיסוי בקודקודים של $G$ : תהי $xy\in E$ ונניח $x\notin U$ ; נראה $y\in U$ .

ראשית, $x\notin U$ יחד עם $x\in V$ גורר $x\notin\hat U$ — אילו היה $x\in\hat U$ , הבנייה הייתה מכניסה אותו ל- $U$ .

כעת נתבונן ב- $v_{xy}\in\hat V$ ; הוא קיים, כי $xy\in E$ ולכן שלב 1 יצר אותו. $\hat U$ שולטת, ולכן $v_{xy}\in\hat U$ או שקיים שכן שלו ב- $\hat U$ .

מקרה 1: $v_{xy}\in\hat U$ . אז בבניית $U$ הכנסנו אחד משכניו — את $x$ או את $y$ . מכיוון ש- $x\notin U$ , בהכרח הכנסנו את $y$ , ולכן $y\in U$ .

מקרה 2: קיים שכן של $v_{xy}$ ב- $\hat U$ . שכניו הם בדיוק $x$ ו- $y$ , ושניהם ב- $V$ . מכיוון ש- $x\notin\hat U$ , בהכרח $y\in\hat U$ ; ומכיוון ש- $y\in V$ , הבנייה הכניסה את $y$ עצמו ל- $U$ .

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

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

זמןO(|V| + |E|)

מקוםO(|V| + |E|)

גודל הפלט|V̂| ≤ |V| + |E|, |Ê| ≤ 3|E|

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

מה זה קונה

$\mathrm{DS}$ היא NP-קשה, ומכיוון שהיא גם ב- $\mathrm{NP}$ — NP-שלמה.

מלכודות

הרדוקציה הזהותית נכשלת. קבוצה שולטת אינה חייבת לכסות קשתות: ב- $K_{1,3}$ (כוכב) המרכז לבדו שולט בכל הגרף וגם מכסה את כל הקשתות, אבל בגרף שהוא זוג קשתות זרות, קבוצה שולטת בגודל $2$ יכולה להיבחר אחרת מכיסוי בגודל $2$ . הכיוון שנשבר הוא זה שדורש תרגום בין "נגיעה בקשת" ל"שליטה בקודקוד", וזה בדיוק מה שקודקוד הקשת $v_{xy}$ עושה.
רדוקציה אינה פותרת. האלגוריתם $R$ אינו יודע מהו $U$ ואינו יודע מהו $\hat U$ — אלה מופיעים רק בהוכחת הנכונות, שבה מותר להניח שקיים פתרון ולבנות ממנו פתרון לצד השני.

השרשרת

נשענת על

IS ≤p VC

מאיפה זה נקרא

שיעור 19משפט 4: $\mathrm{VC}\le_p\mathrm{DS}$ , ולכן $\mathrm{DS}$ היא NP-שלמה
2025הגדרת $\mathrm{DS}$ והוכחת קשיותה.