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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

הקבוצה הבלתי תלויה בכחול

השאלה "בהינתן גרף \ 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-קשה.

ראו גם[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  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