קבוצה בלתי תלויה (תורת הגרפים)

בתורת הגרפים, קבוצה בלתי תלויה (IS - Independent set) היא קבוצת קודקודים בגרף, אשר אין זוג מביניהם המחוברים ישירות דרך קשת אחת. בצביעה חוקית של קודקודים בגרף (כמו זו שבה עוסק משפט ארבעת הצבעים), כל מחלקת צבע היא קבוצה בלתי תלויה. גודל הקבוצה הבלתי תלויה המקסימלית בגרף  מסומן לרוב ב-.
שמאל|ממוזער|160px|הקבוצה הבלתי תלויה בכחול

השאלה "בהינתן גרף  ומספר , האם קיימת בגרף קבוצה בלתי תלויה בגודל "  היא בעיה NP-שלמה והיא אחת מ-21 הבעיות הראשונות לגביהן הוכיח ריצ'רד קארפ כי הן NP-שלמות
. ההוכחה הייתה בעזרת רדוקציה חישובית מבעיית SAT. חיפוש של קבוצה בלתי תלויה שקול לחיפוש של קליקה (תת גרף מלא) בגרף המשלים (שקבוצת הקשתות שלו משלימה את קבוצת הקשתות של הגרף הנתון). בעיה נוספת לה קשר הדוק היא בעיית הכיסוי קודקודים (קבוצת קודקודים "הנוגעת" בכל הקשתות): עבור קבוצה   בלתי תלויה, ההפרש   הוא כיסוי בקודקודים.

לאחר שהתברר שחישוב הגודל המדויק של קבוצה בלתי-תלויה מקסימלית בגרף הוא בעיה קשה, החלו ניסיונות למצוא קירוב לגודל זה. ידוע שלא רק החישוב המדויק, אלא גם קירוב של הגודל עד כדי טעות של  בגרף עם  קודקודים, היא עדיין בעיה NP-שלמה

. האלגוריתם הטוב ביותר הידוע מוצא קירוב שהשגיאה בו היא עד סדר גודל של 
.
באשר לאלגוריתמים מדויקים, זמן הריצה של האלגוריתמים המהירים ביותר הידועים הוא בסביבות 
.  האלגוריתמים המהירים ביותר הידועים המוצאים עבור k נתון אם קיימת קבוצה בלתי תלויה בגודל k מבוססים על כפל מטריצות מהיר, וזמן הריצה שלהם הוא מסדר  כש- הוא המעריך של זמן הריצה של כפל מטריצות - דהיינו לכפול מטריצות  ניתן לביצוע בזמן מסדר   (הערך הידוע של  הוא בסביבות 2.376).

אחת ממחלקות הגרפים הגדולות שעבורן ידועים אלגוריתמים פולינומיים למציאת הקבוצה הבלתי תלויה הגדולה ביותר היא גרפים מושלמים. כך, למשל, מחלקה זו כוללת את הגרפים הדו צדדיים, עבורם ניתן למצוא  את הקבוצה הבלתי תלויה הגדולה ביותר באמצעות אלגוריתם למציאת השידוך הגדול ביותר. לעומת זאת, בגרפים מישוריים הבעיה היא עדיין NP-קשה.

 ראו גם 
 משפט רמזי

קישורים חיצוניים



 הערות שוליים 

קטגוריה:תורת הגרפים
קטגוריה:בעיות NP-שלמות
קטגוריה:אלגוריתמים בתורת הגרפים