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

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