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

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

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

1. בסעיף זה נסתכל על הבעיה $Clique$ עם הפרמטר $k$, המבטא את גודל הקליק. הוכיחו כי קיים אלגוריתם לבעיה זו בעל זמן ריצה $$n^{O(k)}$$ על קלט באורך $n$ עם פרמטר $k$. הסיקו כי יש לה אלגוריתם פרמטרי יעיל חלקית.
2. בסעיף זה נסתכל על הבעיה $Clique$ עם הפרמטר $\Delta$, המבטא את הדרגה המרבית בגרף הקלט $G$. הוכיחו כי קיים אלגוריתם עבור הבעיה בעל זמן ריצה $$O(n^c\cdot2^\Delta)$$ עבור קבוע $c$, כאשר $n$ מייצג את גודל הקלט ו-$\Delta$ את הפרמטר. הסיקו כי יש לה אלגוריתם פרמטרי יעיל.