הצגת המקור של הדף "קבוצה בלתי תלויה (תורת הגרפים)"

ב[[תורת הגרפים]], '''קבוצה בלתי תלויה''' (IS - Independent set) היא קבוצת קודקודים ב[[גרף (תורת הגרפים)|גרף]], אשר אין זוג מביניהם המחוברים ישירות דרך קשת אחת. בצביעה חוקית של קודקודים בגרף (כמו זו שבה עוסק [[משפט ארבעת הצבעים]]), כל מחלקת צבע היא קבוצה בלתי תלויה. גודל הקבוצה הבלתי תלויה המקסימלית בגרף <math>G</math> מסומן לרוב ב-<math>\alpha(G)</math>.
[[תמונה:Independent set graph.gif|שמאל|ממוזער|160px|הקבוצה הבלתי תלויה בכחול]]

השאלה "בהינתן גרף <math>\ G=(V,E) </math> ומספר <math>\ k</math>, האם קיימת בגרף קבוצה בלתי תלויה בגודל <math>\ k</math>"  היא בעיה [[NP-שלמה]] והיא אחת מ-[[NP (מחלקת סיבוכיות)#רשימת 21 הבעיות ה-NP-שלמות של קארפ|21 הבעיות הראשונות]] לגביהן הוכיח [[ריצ'רד קארפ]] כי הן NP-שלמות
{{הערה|1=Richard Karp. Reducibility Among Combinatorial Problems. Proceedings of a Symposium on the Complexity of Computer Computations. 1972.}}. ההוכחה הייתה בעזרת [[רדוקציה חישובית]] מ[[בעיית SAT]]. חיפוש של קבוצה בלתי תלויה שקול לחיפוש של [[קליקה (תורת הגרפים)|קליקה]] (תת גרף מלא) בגרף המשלים (שקבוצת הקשתות שלו [[משלים (מתמטיקה)|משלימה]] את קבוצת הקשתות של הגרף הנתון). בעיה נוספת לה קשר הדוק היא [[בעיית כיסוי קודקודים|בעיית הכיסוי קודקודים]] (קבוצת קודקודים "הנוגעת" בכל הקשתות): עבור קבוצה  <math> I \subset V </math> בלתי תלויה, ה[[הפרש (תורת הקבוצות)|הפרש]] <math>\ V \backslash I</math>  הוא כיסוי בקודקודים.

לאחר שהתברר שחישוב הגודל המדויק של קבוצה בלתי-תלויה מקסימלית בגרף הוא בעיה קשה, החלו ניסיונות למצוא קירוב לגודל זה. ידוע שלא רק החישוב המדויק, אלא גם קירוב של הגודל עד כדי טעות של <math>\ n^{1-\epsilon}</math> בגרף עם <math>n</math> קודקודים, היא עדיין בעיה NP-שלמה
{{הערה|J. Hastad, [http://www.nada.kth.se/~johanh/cliqueinap.ps Clique is hard to approximate within n to the 1-<math>\epsilon</math>], [[Acta Mathematica]], 182:105–142, 1999
}}
{{הערה|1=D. Zuckerman, [http://www.theoryofcomputing.org/articles/main/v003/a006/a006.pdf Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number], Theory of Computing, Volume 3:102-128, 2007}}. האלגוריתם הטוב ביותר הידוע מוצא קירוב שהשגיאה בו היא עד סדר גודל של <math>\ n/\log^2 n</math>
{{הערה|1=M. M. Halldórsson, [http://www.raunvis.hi.is/~mmh/Papers/survey.html Approximations of independent sets in graphs]}}.
באשר לאלגוריתמים מדויקים, זמן הריצה של האלגוריתמים המהירים ביותר הידועים הוא בסביבות <math>\ 2^{n/4}</math>
{{הערה|1=F. V. Fomin,  F. Grandoni, and  D. Kratsch,  [http://www.ii.uib.no/publikasjoner/texrap/pdf/2007-359.pdf A Measure & Conquer Approach for the Analysis of Exact Algorithms]}}.  האלגוריתמים המהירים ביותר הידועים המוצאים עבור k נתון אם קיימת קבוצה בלתי תלויה בגודל k מבוססים על [[כפל מטריצות]] מהיר, וזמן הריצה שלהם הוא מסדר <math>\ n^{\omega k/3}</math> כש-<math>\ \omega</math> הוא המעריך של זמן הריצה של כפל מטריצות - דהיינו לכפול מטריצות <math>n \times n</math> ניתן לביצוע בזמן מסדר <math>\ n^\omega</math>  (הערך הידוע של <math>\ \omega</math> הוא בסביבות 2.376){{הערה|1=G. J. Woeginger, Space and Time Complexity of Exact Algorithms: Some Open Problems, IWPEC 2004: 281-290}}.

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

== ראו גם ==
* [[משפט רמזי]]

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{MathWorld}}

== הערות שוליים ==
{{הערות שוליים|יישור=שמאל}}

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