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

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

בצביעה חוקית של קודקודים (כלומר, סימון כל קודקוק בצבע כך ששני קודקודים סמוכים אינם באותו צבע) כל מחלקת צבע היא קבוצה בלתי תלויה. גודל הקבוצה הבלתי תלויה המקסימלית מסומן בדרך כלל ב-α(G).

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

חיפוש קבוצה בלתי תלויה שקול לחיפוש קליקה (תת-גרף מלא, כלומר קבוצה של קודקודים שכל זוגם מחובר) בגרף המשלים. בגרף המשלים מחברים בדיוק את הזוגות שלא היו מחוברים בגרף המקורי.

קשר נוסף הוא עם כיסוי קודקודים: אם I היא קבוצה בלתי תלויה, אז ההשלמה V\I היא כיסוי קודקודים, כלומר קבוצה שנוגעת בכל הקשתות.

לא רק חישוב המדויק הוא קשה; גם קירוב טוב הוא קשה. ידוע שקירוב בתוך גורם של n^{1-ε} הוא NP-קשה. האלגוריתם הטוב ביותר המוכר נותן קירוב ברמת סדר של n/log^2 n.

באשר לאלגוריתמים מדויקים, הזמנים הטובים הידועים הם אקספוננציאליים, בסדר גודל של 2^{n/4}. אלגוריתמים לתיקון לפרמטר k משתמשים בכפל מטריצות מהיר וזמני ריצה מסדר n^{ω k/3}, כאשר ω הוא המעריך של כפל מטריצות (הערך הידוע שלו הוא כ-2.376).

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

קבוצה בלתי תלויה היא קבוצה של נקודות (קודקודים) בגרף. נקודות בקבוצה כאלו לא מחוברות זו לזו.

אם צובעים את הקודקודים כך ששכנים לא מקבלים את אותו צבע, כל צבע נותן קבוצה כזו.

סימול נפוץ לגודל הגדול ביותר הוא α של הגרף.

השאלה: האם יש קבוצה בלתי תלידה בגודל מסוים? זו שאלה קשה מאוד. ריצ'רד קארפ הראה שהיא קשה בעזרת בעיה לוגית שנקראת SAT (בעיה עם נוסחאות לוגיקה).

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

ההפך של קבוצה בלתי תלידה הוא כיסוי קודקודים. כיסוי קודקודים זה קבוצת נקודות שנוגעת בכל הקשתות בגרף.

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