Egy gráfhoz minimális csúcslefedést találni NP-nehéz. Ezzel szemben tetszõleges maximális párosításból kiindulva, az abban szereplő csúcsok beválasztásával olyan megoldást kapunk, mely a minimális lehetséges elemszámnak legfeljebb kétszerese. Érdekes módon, habár tudtak ebből a 2-es approximációs faktorból lefaragni, ezek a javítások mind o(1) mértékûek voltak. (A jelenlegi legjobb hatékony közelítõ algoritmus a problémához Karakostas-é, melynek approximációs faktora 2-Omega(1/sqrt{log n})).

A másik oldalról annyi ismert, hogy olyan csúcslefedést NP-nehéz konstruálni, melynek mérete a minimálisénak legfeljebb 1,36-szorosa. Ez elég messze van a 2-től, de ennél élesebb alsó becslés egyelőre csak erősebb sejtésekre alapozva adható. Az előadáson egy ilyen eredményről lesz szó, mely Khot és Regev nevéhez fűződik: ha teljesül a Unique Games sejtés, akkor semmilyen 2-nél kisebb s konstansra nem létezik hatékony s-közelítése a problémának.