Jaroslav Nešetřil převzal Nerodovu cenu za průkopnickou práci v teorii grafů

Jaroslav Nešetřil (na snímku uprostřed) získal spolu s francouzským matematikem Patricem Ossonem de Mendez (vpravo) Nerodovu cenu 2025 Evropské asociace pro teoretickou informatiku (EATCS) za průkopnickou práci v teorii grafů, konkrétně za rozvoj konceptu „sparsity“ (řídkosti). Jejich práce významně ovlivnila nejen čistou matematiku, ale má i praktické aplikace v algoritmické teorii grafů, složitosti algoritmů a matematické logice.

Profesor Jaroslav Nešetřil je členem Učené společnosti. Působí na Informatickém ústavu UK (IUUK), stejně jako profesor Patrice Ossona de Mendez, který má další afiliaci na pařížské École des hautes études en sciences sociales (EHESS). Cenu převzali ve Varšavě.

Nerodova cena se uděluje za výjimečné práce v oblasti víceproměnných algoritmů a je pojmenována po významném americkém matematikovi a logikovi Anilu Nerodovi. Oceňuje trvalý přínos, který posunul hranice oboru. Ocenění se uděluje za jednu nebo sérii prací publikovaných v posledních patnácti letech a jeho laureáty vybírá komise složená z předních odborníků.

Letošní cena byla udělena za zásadní příspěvek, který položil základy „sparsity“ – oblasti strukturální teorie grafů, jež se zaměřuje na pojmy „nikde hustých“ tříd grafů a tříd grafů s omezenou expanzí. Tyto dvě definice pevně zachycují koncept lokální, strukturální řídkosti grafů a konečných struktur. Ve své oceňované sérii článků i ve své monografii Sparsity vydané v roce 2012 nakladatelstvím Springer zavedli Nešetřil a Ossona de Mendez klíčové pojmy a ukázali jejich fundamentální povahu. Podařilo se jim dokázat širokou škálu vlastností a ekvivalentních charakterizací, čímž vytvořili mocný soubor technik pro práci s řídkými grafy a strukturami.

Jak již ukázaly jejich předchozí práce, tento soubor nástrojů lze použít k navrhování parametrizovaných algoritmů pro problémy lokální povahy. Během let to vedlo k několika přelomovým výsledkům v parametrizované složitosti, zejména k velkým pokrokům v pochopení složitosti problémů definovatelných v logice prvního řádu.

Průkopnické dílo Nešetřila a Ossony de Mendeze propojilo strukturální teorii grafů s logikou a víceproměnnou algoritmikou, a zanechalo tak trvalou stopu ve všech těchto oborech. Práce obou vědců byla podpořena synergickým grantem Evropské výzkumné rady (ERC).

Foto IUUK

upraveno podle článku na webu MFF UK