רדוקציות

CLIQUE ≤p INDEPENDENT-SET

הכיוון ההפוך, גם הוא באמצעות משלים הגרף. יחד עם INDEPENDENT-SET ≤p CLIQUE, זה מראה ששתי הבעיות שקולות בזמן פולינומיאלי.

שתי הבעיות

CLIQUE
מופע: גרף לא מכוון G ומספר שלם חיובי k.
שאלה: האם G מכיל קבוצה של k צמתים שכל זוג בה מחובר בקשת?
INDEPENDENT-SET
מופע: גרף לא מכוון G′ ומספר שלם חיובי k.
שאלה: האם G′ מכיל קבוצה של k צמתים ללא אף קשת בין שניים מהם?

הבנייה

בהינתן מופע CLIQUE ⟨G, k⟩, בנו מופע INDEPENDENT-SET ⟨G′, k⟩ כאשר G′ הוא המשלים של G:

  1. ל־G′ יש אותה קבוצת צמתים כמו ל־G.
  2. עבור כל זוג u ≠ v של צמתים: u–v היא קשת ב־G′ אם ורק אם u–v אינה קשת ב־G.
  3. השתמשו באותו סף k.

בניית המשלים בודקת כל אחד מ־n(n−1)/2 הזוגות פעם אחת, כך שהרדוקציה רצה בזמן O(n²).

המחשה

שלב 1 / 4מופע CLIQUE
G (קלט)G′ (משלים)1234512345

קלט ⟨G, k⟩ עם k = 3. הצמתים המודגשים S = {1, 3, 5} יוצרים קליקה ב־G — כל זוג מחובר בקשת.

נכונות

(⇒) אם S ⊆ V(G) היא קליקה בגודל k ב־G, אז לכל זוג ב־S יש קשת ב־G. לפי הגדרת המשלים, לאף זוג ב־S אין קשת ב־G′. לכן S היא קבוצה בלתי־תלויה בגודל k ב־G′.
(⇐) אם S ⊆ V(G′) היא קבוצה בלתי־תלויה בגודל k ב־G′, אז לאף זוג ב־S אין קשת ב־G′, כלומר לכל זוג ב־S יש קשת ב־G. לכן S היא קליקה בגודל k ב־G.
לפיכך ⟨G, k⟩ ∈ CLIQUE אם ורק אם ⟨G′, k⟩ ∈ INDEPENDENT-SET, וההעתקה G ↦ G′ ניתנת לחישוב בזמן פולינומיאלי. ∎