מפת הסיבוכיות
EN
תרגיל

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

המרת סף קבוצה בלתי־תלויה לסף כיסוי קודקודים באמצעות משלים קבוצת הקודקודים.

שאלה

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

רמז 1

אם SS בלתי־תלויה, כל קשת חייבת לגעת ב-V∖SV\setminus S.

רמז 2

קשרו בין שני הגדלים באמצעות ∣V∣|V|.

בנייה מודרכת

קבוצה בלתי תלויה → כיסוי קודקודים

שלב 1 מתוך 6
קבוצה בלתי־תלויה לכיסוי קודקודים דרך משלים קבוצהקבוצה בלתי־תלויה במסלול מושלמת לכיסוי קודקודים בעוד שהסף הופך ל־n פחות k.אותו גרף G1234

פתרון מלא

משאירים את אותו גרף GG ומציבים k′=∣V∣−kk'=|V|-k. ההעתקה (G,k)↦(G,∣V∣−k)(G,k)\mapsto(G,|V|-k) פולינומית בבירור.

טענה: S⊆VS\subseteq V קבוצה בלתי־תלויה אם ורק אם V∖SV\setminus S כיסוי קודקודים. אכן, SS בלתי־תלויה בדיוק כאשר אין קשת ששני קצותיה ב-SS, וזה בדיוק אומר שכל קשת נוגעת ב-V∖SV\setminus S.

לכן יש קבוצה בלתי־תלויה בגודל kk אם ורק אם יש כיסוי בגודל ∣V∣−k|V|-k.

Vertex Cover שייכת ל-NP באמצעות תעודת כיסוי בגודל k′k'. עם NP-שלמות של Independent Set מתקבלת NP-שלמות של Vertex Cover.

נקודת ביקורת

כאן משתמשים במשלים קבוצת קודקודים, לא במשלים גרף. הפרמטר חייב להשתנות: k↦∣V∣−kk\mapsto |V|-k.

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

  • השארת k′=kk'=k, ההופכת את המשמעות.
  • בלבול עם כיסוי קשתות או קבוצה שולטת.
  • טענת הזהות בלי לבדוק קשתות הנוגעות ב-SS ובמשלים.

הערת מקור

זו הצגה עצמאית של הדואליות הסטנדרטית IS/VC הנלמדת בשיעורי בעיות הגרפים ומתיישרת עם Sipser / Garey–Johnson. אינה תעתיק ממבחן בודד.

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

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

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