IS ≤p CLIQUE

הבנייה

על קלט $\langle G,K\rangle$ כאשר $G=(V,E)$ ו- $K\in\mathbb{N}$ :

בנה את הגרף המשלים $\bar G=(V,\bar E)$ , כאשר $\bar E=\Big\{xy\ \Big|\ x,y\in V,\ x\ne y\Big\}\setminus E=\binom{V}{2}\setminus E .$
החזר $\langle\bar G,K\rangle$ .

המספר $K$ נשאר ללא שינוי; רק הגרף מתהפך.

המחשה

קשת מקור (נמחקת)קשת משלים (נוספת)

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

IS ∈ ⟹ CLIQUE ∈

נניח $\langle G,K\rangle\in\mathrm{IS}$ . אזי קיימת $U\subseteq V$ עם $|U|=K$ שהיא בלתי תלויה ב- $G$ .

נתבונן באותה $U$ בתוך $\bar G$ — מותר, שכן לשני הגרפים אותה קבוצת קודקודים $V$ . אז $U\subseteq V$ ו- $|U|=K$ . נותר להראות ש- $U$ קליקה ב- $\bar G$ : יהיו $x,y\in U$ שונים. מכיוון ש- $U$ בלתי תלויה ב- $G$ מתקיים $xy\notin E$ , ולפי הגדרת המשלים כל זוג קודקודים שונים שאינו קשת ב- $E$ הוא קשת ב- $\bar E$ ; לכן $xy\in\bar E$ . מכאן ש- $U$ קליקה ב- $\bar G$ , כלומר $\langle\bar G,K\rangle\in\mathrm{CLIQUE}$ .

CLIQUE ∈ ⟹ IS ∈

נניח $\langle\bar G,K\rangle\in\mathrm{CLIQUE}$ . אזי קיימת $U\subseteq V$ עם $|U|=K$ שהיא קליקה ב- $\bar G$ (חובה לומר באיזה גרף — יש כאן שניים).

נתבונן באותה $U$ בתוך $G$ . אז $U\subseteq V$ ו- $|U|=K$ . יהיו $x,y\in U$ שונים. מכיוון ש- $U$ קליקה ב- $\bar G$ מתקיים $xy\in\bar E$ , ולפי הגדרת המשלים $xy\notin E$ . מכאן ש- $U$ בלתי תלויה ב- $G$ , כלומר $\langle G,K\rangle\in\mathrm{IS}$ .

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

זמןO(|V|²) with an adjacency matrix

מקוםO(|V|²)

גודל הפלטO(|V|²)

בייצוג מטריצת שכנויות בדיקת "האם $xy\in E$ " עולה $O(1)$ , ולכן מעבר על כל $\binom{|V|}{2}$ הזוגות עולה $O(|V|^2)$ . בייצוג רשימת קשתות, סריקה עבור כל זוג נותנת $O(|V|^2\cdot|E|)$ . שניהם פולינומיים, ולכן לצורך הטענה אין ביניהם הבדל — וזו בדיוק הסיבה שמותר להתרשל בפרטי המימוש.

מה זה קונה

$\mathrm{IS}$ אינה קשה יותר מ- $\mathrm{CLIQUE}$ . יחד עם הרדוקציה ההפוכה מתקבל ששתי הבעיות שקולות תחת $\le_p$ : אחת מהן ב- $\mathrm P$ אם ורק אם השנייה ב- $\mathrm P$ , ואחת מהן NP-שלמה אם ורק אם השנייה NP-שלמה.

מלכודות

"נמחק את קשתות הקליקה" — נפסל מיד: הרדוקציה אינה יודעת למצוא קליקה, וכל העניין הוא שאיננו יודעים לפתור את הבעיה. אותה מלכודת מוכרת מחישוביות: ברדוקציה מ- $\mathrm{HALT}$ אי אפשר לבדוק אם הקלט בשפה.
"נמחק את כל הקשתות" — אז הפלט לעולם אינו ב- $\mathrm{CLIQUE}$ (עבור $K\ge2$ ), ללא תלות בקלט; זה הורס את כיוון ה"אם". "נוסיף את כל הקשתות" — אז הפלט תמיד ב- $\mathrm{CLIQUE}$ ; זה הורס את הכיוון השני. כל פעולה שמייצרת פלט קבוע-מראש מקלקלת אחד הכיוונים, ולכן צריך פעולה שמחליפה ולא כזו שמאפסת.

הבנייה

המחשה

קבוצה בלתי תלויה → קליקה