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

נגדיר את בעיית $IS$:

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

1. נתונה הרדוקציה הבאה מ-$SAT$. לכל פסוקית יוצרים קודקוד עבור כל השמה המספקת את הפסוקית; מחברים לקליקה את כל הקודקודים השייכים לאותה פסוקית; ומחברים קודקודים השייכים לפסוקיות שונות אם ההשמות החלקיות שהם מייצגים אינן עקביות. אם מספר הפסוקיות הוא $m$, מחזירים גם את המספר $m$.

   הוכיחו את נכונות הבנייה ונתחו את זמן הריצה שלה. האם זמן הריצה פולינומי?

2. הוכיחו כי $IS$ היא $NP$-שלמה.

3. נגדיר את $MAX\text{-}IS$ כבעיית ההכרעה שבה נשאל אם גודל הקבוצה הבלתי תלויה המקסימלית הוא בדיוק $k$. הוכיחו כי $MAX\text{-}IS$ היא $NP$-קשה.