רדוקציות

INDEPENDENT-SET ≤p CLIQUE

רדוקציה קלאסית בזמן פולינומיאלי באמצעות משלים הגרף. אותה קבוצת צמתים היא קבוצה בלתי־תלויה ב־G אם ורק אם היא קליקה במשלים G̅.

שתי הבעיות

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

הבנייה

בהינתן מופע INDEPENDENT-SET ⟨G, k⟩, בנו מופע CLIQUE ⟨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מופע INDEPENDENT-SET
G (קלט)G′ (משלים)1234512345

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

נכונות

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