The 2018 EATCS-IPEC Nerode Prize has been awarded to the paper "Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal" by Stefan Kratsch and our colleague Magnus Wahlström.
The EATCS-IPEC Nerode Prize for outstanding papers in the area of multivariate algorithmics is presented annually with the presentation taking place at IPEC (International Symposium on Parameterized and Exact Computation). The 2018 award will be presented at ALGO/IPEC 2018, which will be held on 22–24 August 2018 in Helsinki, Finland.
The Prize is named in honor of Anil Nerode in recognition of his major contributions to mathematical logic, theory of automata, computability and complexity theory.
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 – published in ACM Transactions on Algorithms 10(4): 20:1-20:15, 2014 – 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.
