אלגוריתם פולינומיאלי לClique?
היי, במהלך פתרון תרגיל בסיבוכיות, אני חושב שמצאתי אלגוריתם פולינומיאלי לבעיית Clique, או יותר נכון- לוואריאציה שלה: קלט: גרף G ומספר טבעי K. שאלה: האם קיים בG קליק בגודל בדיוק K? האלגוריתם שלי הוא הבא: נמצא את כל הקודקודים בגרף שדרגתם בדיוק K-1 (בזמן לכל היותר n^2 כאשר n הוא מספר הקודקודים), נניח שיש t כאלו. עבור כל אחד מהם, נבדוק האם K-1 שכניו גם הם מדרגה K-1. אם כן, אז קיים קליק בגודל בדיוק K. אחרת, לא קיים כזה. איפה הטעות בפתרון שלי? תודה, גיל.
היי, במהלך פתרון תרגיל בסיבוכיות, אני חושב שמצאתי אלגוריתם פולינומיאלי לבעיית Clique, או יותר נכון- לוואריאציה שלה: קלט: גרף G ומספר טבעי K. שאלה: האם קיים בG קליק בגודל בדיוק K? האלגוריתם שלי הוא הבא: נמצא את כל הקודקודים בגרף שדרגתם בדיוק K-1 (בזמן לכל היותר n^2 כאשר n הוא מספר הקודקודים), נניח שיש t כאלו. עבור כל אחד מהם, נבדוק האם K-1 שכניו גם הם מדרגה K-1. אם כן, אז קיים קליק בגודל בדיוק K. אחרת, לא קיים כזה. איפה הטעות בפתרון שלי? תודה, גיל.