קבוצה שולטת
ויקיפדיה האנציקלופדיה encyclopedia
בתורת הגרפים, קבוצה שולטת בגרף (G(V,E היא תת-קבוצה D של הצמתים ב-V כך שכל צומת שאינו ב-D מחובר בקשת לפחות לצומת אחד ב-D. דרגת השליטה (γ(G בגרף היא מספר הצמתים הקטן ביותר המהווים קבוצה שולטת בגרף. בעיית הקבוצה השולטת היא בעיה NP-קשה (יותר מכך היא בעיה NP-שלמה), הבודקת בהינתן גרף כלשהו ומספר K, האם קיימת קבוצה שולטת קטנה מ-K.
בעיית הקבוצה השולטת נחקרה החל משנת 1950 אך החלה למשוך תשומת לב מחוקרים בתחום בעיקר החל משנות ה-70. בשנת 1988 היה ידוע על יותר מ-800 מאמרים בנושא שרובם עסקו באלגוריתמים למציאת דרגת השליטה במחלקות מסוימות של גרפים[1].