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

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

השאלה "בהינתן גרף $\ G=(V,E)$ ומספר $\ k$ , האם קיימת בגרף קבוצה בלתי תלויה בגודל $\ k$ " היא בעיה NP-שלמה והיא אחת מ-21 הבעיות הראשונות לגביהן הוכיח ריצ'רד קארפ כי הן NP-שלמות ^[1]. ההוכחה הייתה בעזרת רדוקציה חישובית מבעיית SAT. חיפוש של קבוצה בלתי תלויה שקול לחיפוש של קליקה (תת גרף מלא) בגרף המשלים (שקבוצת הקשתות שלו משלימה את קבוצת הקשתות של הגרף הנתון). בעיה נוספת לה קשר הדוק היא בעיית הכיסוי קודקודים (קבוצת קודקודים "הנוגעת" בכל הקשתות): עבור קבוצה $I\subset V$ בלתי תלויה, ההפרש $\ V\backslash I$ הוא כיסוי בקודקודים.

לאחר שהתברר שחישוב הגודל המדויק של קבוצה בלתי-תלויה מקסימלית בגרף הוא בעיה קשה, החלו ניסיונות למצוא קירוב לגודל זה. ידוע שלא רק החישוב המדויק, אלא גם קירוב של הגודל עד כדי טעות של $\ n^{1-\epsilon }$ בגרף עם $n$ קודקודים, היא עדיין בעיה NP-שלמה ^[2] ^[3]. האלגוריתם הטוב ביותר הידוע מוצא קירוב שהשגיאה בו היא עד סדר גודל של $\ n/\log ^{2}n$ ^[4]. באשר לאלגוריתמים מדויקים, זמן הריצה של האלגוריתמים המהירים ביותר הידועים הוא בסביבות $\ 2^{n/4}$ ^[5]. האלגוריתמים המהירים ביותר הידועים המוצאים עבור k נתון אם קיימת קבוצה בלתי תלויה בגודל k מבוססים על כפל מטריצות מהיר, וזמן הריצה שלהם הוא מסדר $\ n^{\omega k/3}$ כש- $\ \omega$ הוא המעריך של זמן הריצה של כפל מטריצות - דהיינו לכפול מטריצות $n\times n$ ניתן לביצוע בזמן מסדר $\ n^{\omega }$ (הערך הידוע של $\ \omega$ הוא בסביבות 2.376)^[6].

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

ראו גם

משפט רמזי

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

מדיה וקבצים בנושא קבוצה בלתי תלויה בוויקישיתוף

קבוצה בלתי תלויה, באתר MathWorld (באנגלית)

הערות שוליים

^ Richard Karp. Reducibility Among Combinatorial Problems. Proceedings of a Symposium on the Complexity of Computer Computations. 1972.
^ J. Hastad, Clique is hard to approximate within n to the 1- $\epsilon$ , Acta Mathematica, 182:105–142, 1999
^ D. Zuckerman, Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number, Theory of Computing, Volume 3:102-128, 2007
^ M. M. Halldórsson, Approximations of independent sets in graphs
^ F. V. Fomin, F. Grandoni, and D. Kratsch, A Measure & Conquer Approach for the Analysis of Exact Algorithms
^ G. J. Woeginger, Space and Time Complexity of Exact Algorithms: Some Open Problems, IWPEC 2004: 281-290

[1] Richard Karp. Reducibility Among Combinatorial Problems. Proceedings of a Symposium on the Complexity of Computer Computations. 1972.

[2] J. Hastad, Clique is hard to approximate within n to the 1- $\epsilon$ , Acta Mathematica, 182:105–142, 1999

[3] D. Zuckerman, Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number, Theory of Computing, Volume 3:102-128, 2007

[4] M. M. Halldórsson, Approximations of independent sets in graphs

[5] F. V. Fomin, F. Grandoni, and D. Kratsch, A Measure & Conquer Approach for the Analysis of Exact Algorithms

[6] G. J. Woeginger, Space and Time Complexity of Exact Algorithms: Some Open Problems, IWPEC 2004: 281-290

[1]

[2]

[3]

[4]

[5]

[6]