IPEC Nerode Prize 2018 - Nomination

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

Stefan Kratsch, Magnus Wahlström

for their paper

"Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal". ACM Trans. Algorithms 10(4): 20:1-20:15 (2014)


The search for polynomial kernelization algorithms played a central role in the research on parameterized complexity during the last decade. By now, there are well-developed tools for both positive and negative results in this area. Kratsch and Wahlström were the first to recognize the applicability of the matroid-based machinery (developed earlier by Marx, based on classic results of Lovász) to the compression of NP-hard cut problems. Their work settled the long-standing open problem about the polynomial kernelizability of the Odd Cycle Transversal problem in a beautiful way.

The paper, and its follow-up (Representative Sets and Irrelevant Vertices: New Tools for Kernelization. FOCS 2012), have been very influential and paved the way for several other matroid-based kernelizations, such as those for Vertex Multiway Cut, Above-Guarantee Vertex Cover, and Subset Feedback Vertex Set. Moreover, experiments show that matroid-based compression is not merely a nice theoretical concept, but also gives relevant practical speedups (Stefan Fafianie, Stefan Kratsch: An Experimental Analysis of a Polynomial Compression for the Steiner Cycle Problem. SEA 2015: 367-378). For this reason, the Nerode Prize 2018 Committee unanimously decided that the this foundational paper by Kratsch and Wahlström deserves to win the Nerode prize.

e-max.it: your social media marketing partner
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.