נקרא לגרף צנוע אם הדרגה המקסימלית שלו היא לכל היותר 1. 1. הוכיחו כי בעיית ההכרעה הבאה היא NP-שלמה: קלט: גרף פש…

נקרא לגרף צנוע אם הדרגה המקסימלית שלו היא לכל היותר $1$.

1. הוכיחו כי בעיית ההכרעה הבאה היא $NP$-שלמה:

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

   רמז: בצעו רדוקציה מ-$VC$ והוסיפו עלה לכל קודקוד.

2. בגרסת המינימיזציה יש להסיר מספר מינימלי של קודקודים כדי לקבל גרף צנוע. תנו אלגוריתם פולינומי בעל יחס קירוב $3$ והוכיחו את יחס הקירוב.