Új típusú min-max tételek a kombinatorikus optimalizálásban – Frank András levelező tag székfoglaló előadása

A kombinatorikus optimalizálás min-max tételeinek egyik lényeges funkciója, hogy megállási szabályként interpretálhatók, és ezáltal a kiindulópontot jelentik az optimalizálási problémát megoldó hatékony (= polinomiális futásidejű) algoritmus tervezésekor.

Frank András Fotó: mta.hu/ Szigeti Tamás

A székfoglaló előadáson készült fotók galériájaKőnig tétele páros gráfok maximális elemszámú párosításairól, Menger tétele diszjunkt utakról, Lucchesi és Younger tétele digráfok optimális erősen összefüggővé tételéről vagy Edmonds tétele két matroid közös független halmazainak maximális elemszámáról a kombinatorikus optimalizálás klasszikus min-max tételei. Ezek közös jellemzője, hogy mind kiterjeszthetőek a súlyozott/költséges esetekre is, aminek hátterében az a nagyszabású felismerés áll, hogy a szóban forgó objektumok konvex burkát egy teljesen duálisan egészértékű (TDI) lineáris rendszerrel lehet leírni. Ilyenkor ugyanis a lineáris programozás dualitástétele egészértékű optimumokat biztosít. Ez a poliéderes szemlélet különösen eredményesnek bizonyult a szub- és szupermoduláris függvények elméletében, és olyan nehéz gráfoptimalizálási problémák algoritmikus megoldását tette lehetővé, mint egy digráf legolcsóbb gyökeresen k-összefüggő részgráfjának a meghatározása vagy egy gráf legolcsóbb k-él-összefüggő irányításának kiszámítása.

A poliéderes megközelítés erejét jól jelzi, hogy ezen az úton a költséges esetekre vonatkozó min-max tételek igazolása is lehetővé válik. Ez az alapvető vonás azonban azt is mutatja, hogy a poliéderes kombinatorikai megközelítés elvileg nem lehet elegendő olyan esetekben, amikor az elemszám optimalizálási feladat megoldható, míg a költséges változat már NP-teljes. Bár az első ilyen jellegű eredmény Ryser nyomán már 1958-ban felbukkant, csak Watanabe és Nakamura 1987-ben megjelent mély min-max tétele jelezte, hogy itt egy teljesen új jelenség állhat a háttérben. Az előadás e jelenség feltárásának főbb állomásait vázolja fel, bemutatva a létrejövő elmélet korai és legújabb alkalmazásait is.

Megmutatjuk például, hogy Győri Ervin derékszögű poligonok fedésére vonatkozó min-max tétele, Ryser maximum tag-rang (term-rank) tétele, Király Zoltán négyszögmentes 2-párosításokra vonatkozó min-max tétele, illetve a Bérczi Kristóffal közösen igazolt friss eredmény egyszerű k-összefüggő digráfok fokszámsorozatainak jellemzésére mind egyetlen közös tételből adódik. Az elmélet kidolgozásában alapvető szerepet játszottak az Egerváry Kutatócsoport egykori és mai tagjai (többek között ifj. Benczúr András, Bérczi Kristóf, Bernáth Attila, Fleiner Balázs, Fleiner Tamás, Jordán Tibor, Király Tamás, Király Zoltán, Makai Márton, Pap Gyula, Szabó Jácint, Szigeti Zoltán, Végh László).