קבוצה S V היא קבוצה שולטת בגרף G=(V,E) אם לכל v V S קיים שכן ב-S. נגדיר את בעיית DS: קלט: גרף פשוט לא מכוון G=…

קבוצה $S\subseteq V$ היא קבוצה שולטת בגרף $G=(V,E)$ אם לכל $v\in V\setminus S$ קיים שכן ב-$S$. נגדיר את בעיית $DS$:

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

1. 1. הוכיחו שאם ב-$G$ אין קודקודים מבודדים, אז כל כיסוי קודקודים של $G$ הוא גם קבוצה שולטת.
   2. תנו גרף קשיר בעל ארבעה קודקודים שבו גודל הקבוצה השולטת המינימלית שונה מגודל כיסוי הקודקודים המינימלי.
2. הוכיחו כי $DS$ היא $NP$-שלמה. השתמשו ברדוקציה מ-$VC$: הסירו קודקודים מבודדים, ולכל קשת $e=\{u,v\}$ הוסיפו קודקוד $w_e$ השכן ל-$u$ ול-$v$.