A következő kombinatorika szeminárium (X. 26. (péntek), 10:00, Farkas-terem) előadása

Szörényi Balázs: A csúcslefedés nehézsége

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 lefaragani, 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.

Minden érdeklődőt szeretettel várunk,

Péter