הגרף המשלים, בכיוון ההפוך

CLIQUE ≤p IS

$\mathrm{CLIQUE}\le_p\mathrm{IS}$ — אותה רדוקציה בדיוק, המעבר לגרף המשלים, עובדת גם בכיוון ההפוך.

הבנייה

על קלט $\langle H,K\rangle$ עם $H=(V,F)$ גרף: החזר $\langle\bar H,K\rangle$ .

המפתח לנכונות הוא שהמשלים הוא אינוולוציה: $\overline{\bar H}=H,\qquad\text{שכן}\qquad \binom{V}{2}\setminus\left(\binom{V}{2}\setminus F\right)=F .$

המחשה

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

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

CLIQUE ∈ ⟹ IS ∈

נניח $\langle H,K\rangle\in\mathrm{CLIQUE}$ , כלומר קיימת $U\subseteq V$ בגודל $K$ שהיא קליקה ב- $H$ . יהיו $x,y\in U$ שונים; אז $xy\in F$ , ולכן $xy\notin\bar F$ , כלומר $U$ בלתי תלויה ב- $\bar H$ . לכן $\langle\bar H,K\rangle\in\mathrm{IS}$ .

IS ∈ ⟹ CLIQUE ∈

נניח $\langle\bar H,K\rangle\in\mathrm{IS}$ , כלומר קיימת $U\subseteq V$ בגודל $K$ בלתי תלויה ב- $\bar H$ . יהיו $x,y\in U$ שונים; אז $xy\notin\bar F$ , ולכן $xy\in F$ , כלומר $U$ קליקה ב- $H$ . לכן $\langle H,K\rangle\in\mathrm{CLIQUE}$ .

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

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

מקוםO(|V|²)

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

זהה לחלוטין לכיוון ההפוך — זו אותה בנייה.

מה זה קונה

$\mathrm{CLIQUE}\equiv_p\mathrm{IS}$ . זהו המקרה הנקי ביותר של שתי בעיות שקולות: לא רק שקיימות רדוקציות בשני הכיוונים, אלא שזו אותה פונקציה בדיוק.

מלכודות

העובדה ש- $A\le_p B$ אינה גוררת $B\le_p A$ . כאן זה במקרה נכון, בזכות האינוולוציה; זו תכונה של הבנייה הספציפית ולא כלל כללי.

השרשרת

נשענת על

IS ≤p CLIQUE

מאיפה זה נקרא

שיעור 7משפט 4: $\mathrm{CLIQUE} \le_p \mathrm{IS}$
2026 '1 מועד 2שקילות פולינומית בין גרסאות "בדיוק $k$ ", "לפחות $k$ " ו"מקסימלי $k$ " של קליקה.