Skip to main content

Magnus Wahlström was awarded the 2018 Nerode Prize

News

  • Date13 May 2018

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.

Magnus 1

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.

 

Related topics

Explore Royal Holloway

Get help paying for your studies at Royal Holloway through a range of scholarships and bursaries.

There are lots of exciting ways to get involved at Royal Holloway. Discover new interests and enjoy existing ones

Heading to university is exciting. Finding the right place to live will get you off to a good start

Whether you need support with your health or practical advice on budgeting or finding part-time work, we can help

Discover more about our 21 departments and schools

Find out why Royal Holloway is in the top 25% of UK universities for research rated ‘world-leading’ or ‘internationally excellent’

They say the two most important days of your life are the day you were born, and the day you find out why

Discover world-class research at Royal Holloway

Discover more about who we are today, and our vision for the future

Royal Holloway began as two pioneering colleges for the education of women in the 19th century, and their spirit lives on today

We’ve played a role in thousands of careers, some of them particularly remarkable

Find about our decision-making processes and the people who lead and manage Royal Holloway today