EATCS-IPEC Nerode Prize 2019

The EATCS-IPEC Nerode Award Committee has selected the following paper as the recipient of the EATCS-IPEC Nerode Prize 2019:

Noga Alon, Raphael Yuster, and Uri Zwick


Journal of the Association for Computing Machinery, Vol 42, No 4, pp. 844-856 (1995).

The technique of Color-Coding, introduced by Alon, Yuster, and Zwick introduces the following elegant and powerful insight to find occurrences of a k-vertex pattern subgraph H in a larger host graph G: when randomly assigning one out of k colors to each vertex of G, there is a non-negligible probability that all the vertices of any fixed occurrence of the pattern H receive distinct colors. If the pattern H is tree-like, then dynamic programming can be used to efficiently find such an occurrence of the pattern H with distinctly colored vertices.

Color-coding has become a vastly important ingredient in the toolbox of parameterized algorithm design. The technique plays a prominent role in all textbooks on the subject. It has been successfully applied to obtain effective or faster parameterized algorithms for a wide range of problems, including k-path, k-cycle, subgraph isomorphism, packing and matching, graph motif, clustering, motion planning, local search, and graph cut problems. The seminal paper by Alon, Yuster, and Zwick introduces the technique in an accessible way and addresses many related aspects that have become important in parameterized complexity: derandomization, the algorithmic tractability of bounded-treewidth pattern graphs, and speed-ups for input graphs from a proper minor-closed family.

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 this foundational paper by Alon, Yuster, and Zwick be awarded the 2019 Nerode Prize. your social media marketing partner
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.