רדוקציה מקבוצה בלתי־תלויה לקליקה

המרת מופע קבוצה בלתי־תלויה למופע קליקה באמצעות משלים גרף.

שאלה

בהינתן גרף לא־מכוון $G=(V,E)$ ומספר שלם $k$, בנו בזמן פולינומי גרף $G'$ ומספר $k'$ כך שב-$G$ יש קבוצה בלתי־תלויה בגודל $k$ אם ורק אם ב-$G'$ יש קליקה בגודל $k'$. הוכיחו את שני הכיוונים וטענו שהבנייה פולינומית באורך הקלט המקודד.

רמז 1

אותה קבוצת קודקודים יכולה לשרת את שני המופעים. איזו יחס קשתות הופך אי־סמיכות לסמיכות?

רמז 2

הפרמטר אינו חייב להשתנות אם קבוצת הקודקודים נשארת זהה.

פתרון מלא

נגדיר $G'=\overline{G}=(V,\binom{V}{2}\setminus E)$ כגרף המשלים על אותה קבוצת קודקודים, ונציב $k'=k$. רישום כל אי־הקשתות של $G$ אורך $O(|V|^2)$, והוא פולינומי בקידוד הסטנדרטי.

קבוצה $S\subseteq V$ בלתי־תלויה ב-$G$ בדיוק כאשר אין ב-$S$ זוג המחובר בקשת של $E$. שקילות: כל זוג קודקודים שונים ב-$S$ מחובר בקשת של $\overline{G}$, ולכן $S$ קליקה ב-$G'$. הכיוון ההפוך זהה. עבור $|S|=k$ מתקבלת השקילות.

שייכות CLIQUE ל-NP סטנדרטית: קבוצת מועמדים בגודל $k$ היא תעודה, וכל זוג נבדק בזמן פולינומי. יחד עם NP-שלמות של Independent Set (דרך 3SAT) מתקבלת NP-שלמות של CLIQUE.

נקודת ביקורת

הבחינו בין משלים גרף (היפוך קשתות, $k$ קבוע) לבין משלים קבוצת קודקודים (ל־Vertex Cover, שמשנה את הפרמטר).

טעויות נפוצות

• שינוי מיותר של $k$, או שכחת שלולאות אינן קשתות.
• בניית משלים על ידי מחיקת קודקודים במקום היפוך קשתות.
• הוכחת כיוון אחד בלבד.

הערת מקור

זו הצגה עצמאית של זהות סטנדרטית באטלס הרדוקציות של הקורס, מיושרת לספרים (Sipser / Garey–Johnson) ולסיכומי השיעור על IS, CLIQUE ו־VC; אינה תעתיק מילולי של מטלה.

מקורות ואימות

• Merged summary, pp. 55-57
• Sipser 3e, sec. 7.5
• Garey-Johnson, GT19 and GT20
• מיפוי קטלוג: data/exercises.json; הניסוחים והפתרונות נכתבו באופן עצמאי.

פתיחה בגלריית ההמחשות: קבוצה בלתי תלויה → קליקה