בעיית קבוצת קודקודי המשוב

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

בעיית קבוצת קודקודי המשוב היא הבעיה הבאה: בהינתן גרף ומס' טבעי k, האם קיימת קבוצת משוב בגרף בגודל k? בעיה זו היא NP-שלמה בתורת הסיבוכיות. זו אחת מ21 הבעיות ה-NP-שלמות של קארפ, הבעיות הראשונות שהוצגו כבעיות NP-שלמות. לבעיה זו יש שימושים רבים במערכות הפעלה, בסיסי נתונים ותכנון שבב אלקטרוני מסוג VLSI.

הגדרה פורמלית

בעיית ההכרעה הזו מוגדרת באופן הבא:

בהינתן הקלט הבא: גרף (מכוון או לא מכוון) $G=<V,E>$ ומספר טבעי $k$, ענה על השאלה:

האם קיימת תת-קבוצה של הקודקודים $X\subseteq V$ כך שמתקיימים התנאים הבאים:

• $|X|\leq k$
• הגרף $G$ ללא הקודקודים מהקבוצה $X$ הוא חסר מעגלים

כלומר, הגרף $G[V\setminus X]$ שנשאר אחרי הסרת הקודקודים מהקבוצה $X$ הוא יער מושרה (גרף ללא מעגלים). לכן, מציאת קבוצת המשוב המינימלית בגרף שקולה למציאת היער המושרה המקסימלי בגרף.

NP-קושי של הבעיה

ריצ'רד קארפ הראה בשנת 1972 כי הבעיה בגרף מכוון היא NP-קשה. הרדוקציה שקארפ עשה מראה גם את הNP-שלמות של בעיית קבוצת קודקודי המשוב עבור גרף לא מכוון. בעיית קבוצת קודקודי המשוב יכולה להיפתר בזמן פולינומי בגרפים שדרגתם היא לכל היותר 3.

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

אלגוריתם מדויק

בעיית הNP-אופטימיזציה המתאימה למציאת גודל של קבוצת קודקודי משוב ניתנת לפתרון בזמן $O(1.7347^{n})$, כאשר $n$ הוא מספר הקודקודים בגרף. אלגוריתם זה מחשב יער מושרה מרבי, וכאשר יער כזה מתקבל, המשלים שלו הוא קבוצת קודקודי משוב מינימלית. מספר קבוצות קודקודי משוב מינמליים בגרף חסום על ידי $O(1.8638^{n})$. ניתן עדיין למצוא קבוצת קודקודי המשוב בגרף מכוון בזמן $O(1.9977^{n})$, כש$n$ זה מספר הקודקודים בגרף המכוון.

אלגוריתם קירוב

בעיה זו היא APX-שלמה (נובע ישירות מAPX-שלמות של בעיית כיסוי קודקודים). אלגוריתם הקירוב הטוב ביותר עבור הבעיה עם גרף לא מכוון פותרת את הבעיה עם פרמטר קירוב 2, על סמך משפט Becker-Geiger.

יישומים במערכות הפעלה

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