Nagy örömmel osztjuk meg két új publikációnkat, amelyek a Discrete Applied Mathematics folyóiratban jelentek meg. A cikkek első szerzője Pintér József, laborunk tudományos és technológiai vezetőhelyettese. Mindkettő a számítási komplexitás egy-egy nyitott kérdését zárja le, és mindkét esetben a várttal ellentétes válasz született.

A konformálhatóság NP-teljes. A teljes színezés egy gráf csúcsait és éleit együtt színezi úgy, hogy az egymást érintő elemek különböző színt kapjanak. 1988-ban Chetwynd és Hilton a konformálhatóságot ennek a nehéz feladatnak a vizsgálatára vezette be. Egy gráf akkor konformálható, ha létezik olyan szabályos színezése Δ+1 színnel (ahol Δ a maximális fokszám), amelynek színosztályai egy paritási feltételt teljesítenek. Minden olyan gráf konformálható, amely teljesen színezhető Δ+1 színnel, így a konformálhatóság szükséges feltétele az optimális teljes színezésnek. Az, hogy ez a feltétel hatékonyan ellenőrizhető-e, nyitott kérdés volt, és a jelek a hatékony megoldhatóság felé mutattak.

József az ellenkezőjét bizonyítja: a konformálhatóság eldöntése NP-teljes. A nehézség akkor is fennáll, ha a gráf összefüggő, reguláris, páratlan rendű, függetlenségi száma három, fokszáma pedig legalább a csúcsok számának fele. A bizonyítás a perfekt háromszög-pakolási problémából indul ki, és egy új regularizációs lemmára épül, amely egy K₄-mentes gráfot úgy tesz regulárissá, hogy egyetlen háromszöget sem hoz létre vagy szüntet meg. Ez az eszköz a cikken túl is hasznos lehet. Az eredmény lezárja az általános komplexitási kérdést, és megmutatja, hogy a regularitás önmagában nem dönti el, hová esik egy gráfosztály: a ritka és a páros reguláris gráfok esetén a feladat hatékonyan megoldható, a kis függetlenségi számú, sűrű reguláris gráfok esetén viszont nehéz.

Kevés gyorsítótár, gyors válaszok. Amikor emberek milliói nézik ugyanazt a sorozatot, az olyan szolgáltatások, mint a Netflix, a népszerű tartalmakat a nézőkhöz közeli gyorsítótárakban tárolják. Az, hogy mit érdemes hol tárolni, ha a gyorsítótárak kapacitása korlátos, és minden felhasználó csak néhány gyorsítótárat ér el, a hálózati gyorsítótárazási probléma. A feladat általános esetben NP-nehéz. Az AAAI 2025 konferencián Ganian, Mc Inerney és Tsigkari megkezdte a probléma parametrizált komplexitásának vizsgálatát. Az egyforma méretű tartalmakat feltételező, homogén változatra hat olyan parametrizálást azonosítottak, amelyek státuszát nem tudták eldönteni. Megmutatták, hogy ez a hat eset egymással együtt áll vagy bukik, és azt sejtették, hogy mindegyikük W[1]-nehéz.

József Stangl Reginával közösen írt cikkében ellenkező irányban zárja le az egész családot. A szerzők bebizonyítják, hogy a probléma fixparaméteresen kezelhető a gyorsítótárak számára nézve: rögzített számú gyorsítótár esetén a futási idő polinomiális a bemenet méretében, és ebből mind a hat nyitott eset következik. A kulcsmegfigyelés egy rejtett blokkstruktúra. C gyorsítótár esetén minden tartalomnak csak 2^C lehetséges elhelyezési mintázata van, és a különböző tartalmak csak a C kapacitáskorláton keresztül hatnak egymásra. Ez pontosan egy n-szeres egészértékű program alakja, amelyre gyors algoritmusok ismertek. A sejtés eldöntésén túl a megfogalmazás tömör, egzakt modellt ad a kevés gyorsítótárat tartalmazó példányokhoz.

Gratulálunk Józsefnek és Reginának a publikációkhoz!

A konformálhatóság NP-teljessége: https://www.sciencedirect.com/science/article/pii/S0166218X26005457?via%3Dihub

Hálózati gyorsítótárazás a gyorsítótárak száma szerint parametrizálva: https://www.sciencedirect.com/science/article/pii/S0166218X26005548?via%3Dihub