Fedor V. Fomin - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday

More information about this series at http://www.springer.com/series/7407

Cover illustration drawn by Fedor V. Fomin

This Springer imprint is published by the registered company Springer Nature Switzerland AG

The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland

Hans L. Bodlaender (photo by Ivar Pel)

This Festschrift celebrates the contributions of Hans L. Bodlaender on the occasion of his 60th birthday. Hans has made many transformative discoveries in algorithms research, complexity theory, and graph theory, as is evidenced in the articles of this volume.

The most well-known results by Hans come from his deep and thorough investigations into thetreewidthof graphs. Intuitively defined as a measure of how close a graph resembles a tree, treewidth can be exploited by algorithms to solve many computational problems much faster on graphs of small treewidth than is possible in general. Finding efficient algorithms to determine whether a graph actually has small treewidth has fascinated Hans for many years. One of his defining contributions in the area is a linear-time algorithm for computing treewidth on graphs of bounded treewidth. This result has influenced the field so profoundly that it has become known asBodlaenders theorem. It is a truly rare feat to have a named result, which speaks to the remarkable researcher that Hans is.

Hans interest in treewidth proved a gateway to broader investigations into graph algorithms and graph theory. His deep knowledge and brilliant problem-solving abilities led to many diverse results in these areas and paved the way for many fellow researchers to pursue similar research directions. For example, he chairs the Steering Committee of the International Workshop on Graph-Theoretic Concepts in Computer Science and organized it twice. At the same time, Hans enthusiasm inspired students of his lectures to explore this wondrous world and this led quite a few of those students to become researchers in graph algorithms themselves.

Treewidth as a graph parameter naturally steered Hans to the blossoming field ofparameterized algorithms and complexity. A central notion in this field is that of a kernel: effectively a polynomial-time preprocessing heuristic with provable guarantees on the reduction in instance size that it achieves. Together with Rod Downey, Mike Fellows, and Danny Hermelin, Hans developed a framework to prove limitations of kernels, in that some problems do not admit kernels that reduce a problem to size polynomial in the parameter. This framework ushered in a new era in parameterized algorithms and guided many new investigations into the kernelization complexity of computational problems. The paper won Hans and his coauthors the EATCS-IPEC Nerode Prize 2014 for outstanding papers in the area of multivariate algorithmics.

The fact that Hans enjoys mathematical and computational puzzles naturally spills into the real world, where Hans enjoys puzzles and board games. Conversely, his interest in puzzles and board games led him to define and study new problems on the computational complexity of these games. Hence, Hans sees beautiful puzzles everywhere and excudes great joy solving them every day.

The Festschrift will be presented to Hans, as a surprise, at the workshop Graph Decompositions: Small Width, Big Challenges at the Lorentz Center in Leiden in April 2020. It contains short personal contributions and surveys on the topics that have defined Hans career.

Many congratulations on your birthday, Hans! Please enjoy this Festschrift and we hope for many years of beautiful science to come!

Finally, we wish to thank the people that made this volume possible. In particular, we thank all the authors for their wonderful contributions and for reviewing and proofreading. We also thank Alfred Hofmann and Anna Kramer at Springer for making the volume possible and for their support.