EATCS-IPEC Nerode Prize 2024

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

Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos

for their paper

(Meta) Kernelization. J. ACM 63(5): 44:1-44:69 (2016), announced at Foundations of Computer Science (FOCS) 2010.

Laudatio:

Kernelization is a fundamental technique for the design and analysis of parameterized algorithms. The Nerode Prize 2024 is awarded for two algorithmic meta-theorems about the kernelization of problems on graphs of bounded genus under certain coverability properties: problems expressible in Counting Monadic Second Order Logic admit a polynomial kernel, and problems of finite integer index admit a linear kernel. These results unify previously known results on the kernelization complexity of problems on planar and bounded genus graphs, improve and generalize several of them, provide new results for additional problems, and fundamentally deepen our understanding of kernelization. To establish these results, the authors introduce a new combinatorial decomposition theorem (“protrusion decomposition”), and algebraic reductions to replace the pieces that are part of such a decomposition (“protrusion replacement”), both of which have had high impact and led to further applications.

This paper has been one of the most influential papers both in kernelization and parameterized complexity of problems on planar and “almost-planar” graphs and is one of the most significant positive achievements since the inception of the field.

Nerode Prize Committee 2024: Thore Husfeldt (chair), Sang-il Oum, Russell Impagliazzo