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

נסתכל על בעיית כיסוי הקודקודים $VC$:

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

1. הוכיחו כי קיים אלגוריתם לבעיה זו בעל זמן ריצה $$n^{O(k)}$$ על קלט באורך $n$ עם פרמטר $k$. הסיקו כי לבעיה $VC$ עם הפרמטר $k$ יש אלגוריתם פרמטרי יעיל חלקית.
2. בסעיף זה נרצה להראות כי לבעיה $VC$ עם הפרמטר $k$ יש אלגוריתם פרמטרי יעיל.

   1. יהא $G=(V,E)$ גרף ותהא $\{u,v\}$ קשת של $G$. הוכיחו כי כל כיסוי קודקודים של $G$ כולל לפחות את אחד מן הקודקודים $u,v$.

   2. הוכיחו כי קיים אלגוריתם עבור הבעיה $VC$ בעל זמן ריצה

      $$O(n^c\cdot2^k)$$

      עבור קבוע $c$, כאשר $n$ מייצג את גודל הקלט ו-$k$ את הפרמטר.

      הדרכה: השתמשו באלגוריתם רקורסיבי ובטענה מהסעיף הקודם.

   3. הסיקו כי לבעיה $VC$ עם הפרמטר $k$ יש אלגוריתם פרמטרי יעיל.