EATCS-IPEC Nerode Prize 2025

The EATCS-IPEC Nerode Prize for outstanding papers in the area of multivariate algorithmics is awarded to

Jaroslav Nešetřil and Patrice Ossona de Mendez

for their papers

• "Grad and classes with bounded expansion I. Decompositions", European Journal of Combinatorics 29(3): 760–776, 2008;
• "Grad and classes with bounded expansion II. Algorithmic aspects", European Journal of Combinatorics 29(3): 777–791, 2008;
• "First order properties on nowhere dense structures", Journal of Symbolic Logic, 75(3): 868–887, 2010;
• "On nowhere dense graphs", European Journal of Combinatorics 32(4): 600–617, 2011.

Laudatio:

Nerode Prize 2025 is awarded for laying foundations of Sparsity: an area of structural graph theory centered around the concepts of nowhere dense graph classes and graph classes with bounded expansion. These two definitions robustly capture the concept of local, structural sparseness in graphs. In the distinguished series of papers, as well as in their book Sparsity, Nešetřil and Ossona de Mendez introduced the key notions and demonstrated their fundamental character by proving a wide range of properties and equivalent characterizations. The outcome is a powerful toolbox of techniques for working with sparse graphs. As already observed in the work of Nešetřil and Ossona de Mendez, this toolbox can be used to design parameterized algorithms for problems of local nature. Over the years, this has led to several landmark results in parameterized complexity, in particular to major advances in understanding the complexity of problems definable in First Order logic.

Consequently, the groundbreaking work of Nešetřil and Ossona de Mendez created an impressive bridge between structural graph theory, logic, and multivariate algorithmics, making a lasting and far-reaching impact on all those fields.

Nerode Prize Committee: Sang-il Oum (chair), Russell Impagliazzo, Michał Pilipczuk