EATCS-IPEC Nerode Prize 2020The EATCS-IPEC Nerode Award Committee has selected the following paper as the recipient of the EATCS-IPEC Nerode Prize 2020:
The concept of important separators, and the related concept of important cuts have become elegant and efficient tools frequently used to establish the fixed parameter tractability of graph problems. The first awarded paper introduces the notion of important separators and establishes many combinatorial and algorithmic insights. The paper gives a combinatorial bound on the number of important separators, and then uses this bound to obtain multiple important algorithmic applications. To accomplish this, the paper provides elegant proofs that show that optimal solutions contain an important separator with specific characteristics. The approach is robust in the sense that it works for a large variety of problems. After the framework was established, several followup papers showed fixed parameter tractability for well-studied graph problems using the new technology, while introducing refinements and extensions of the techniques. The second awarded paper is a striking example of this, giving the first FPT algorithm for the famous directed feedback vertex set problem, thus solving one of the most important and long-standing open problems of the field. Based on its excellent technical exposition and its introduction of a seminal technique that has led to many key research directions in parameterized complexity, the Nerode Prize Committee unanimously voted that these foundational papers by Marx, D., Chen, J., Liu, Y., Lu, S., O’Sullivan, B. and Razgon, I. be awarded the 2020 Nerode Prize. |
