EATCS-IPEC Nerode Prize 2023The EATCS-IPEC Nerode Award Committee consisting of Fedor V. Fomin (chair), Thore Husfeldt, and Sang-il Oum, has selected the following paper as the recipient of the EATCS-IPEC Nerode Prize 2023:
Appraisal The paper solved a major open problem in parameterized complexity, with numerous consequences and bounds improved. It deals with so-called graph connectivity problems, where the goal is to find in a given graph a structure that, in addition to other constraints, is connected. This is a broad class of fundamental problems, including Steiner Tree, Hamiltonian Cycle, Connected Vertex Cover, and Feedback Vertex Set. The paper focuses on these problems parameterized by the width of the given tree decomposition of the input graph. The paper introduces a new generic technique called cut-and-count. The technique brings drastic improvements in the running times of many state-of-the-art dynamic programming algorithms on graphs of bounded treewidth. By now, cut-and-count has become one of the classic techniques in parameterized complexity. The main insight of the Nerode Award paper–dynamic programming does not need to track all the partial solutions–-paved the road to many other important results in graph algorithms. For this reason, the Nerode Prize 2023 Committee unanimously decided that this breakthrough paper by Cygan, Nederlof, Pilipczuk, Pilipczuk, van Rooij, and Wojtaszczyk deserves to win the Nerode prize. |
