Leírás
Egy gráfban keresünk k diszjunkt feszítő fát úgy, hogy a legtöbbet használt él a lehető legkevesebb
fában legyen. Ezen belül, a második legtöbbet használt él a legkevesebb fában legyen, ezen belül, a harmadik
legtöbbet használt él a lehető legkevesebb fában legyen, és így tovább. Egy analóg problémában
egy gráfnak keresünk erősen összefüggő irányítását, amelyben a legnagyobb befok a lehető legkisebb, ezen
belül a következő legnagyobb befok a lehető legkisebb, stb. Az ilyen típusú feladatokat nevezik egalitárius,
más források "shifted" optimalizálási feladatnak. Az előadásban az előzmények áttekintése után bemutatom
azokat az új eredményeket, melyeket Kazuo Murotával közösen értünk el. Például igazolni tudjuk
azt a korábban megfogalmazott sejtést, hogy ha egy gráf valamely erősen összefüggő irányításában már nem
létezik egy kézenfekvő lokális javítás, akkor az irányítás egalitárius. Hasonlóképp, meg tudjuk oldani a fenti
fa-pakolós egalitárius feladat fenyő-pakolós változatát. Arra is kidolgoztunk egy erősen polinomiális algoritmust,
hogy egy kapacitásos digráfban miként lehet egy K nagyságú megengedett egalitárius st-folyamot
kiszámolni. Itt már az a speciális eset is érdekes, amikor a legkisebb olyan \beta értéket keressük, amelyre
valamennyi \beta-nál nagyobb kapacitást lecsökkentve még mindig van K nagyságú megengedett st-folyam.