Hans Bodlaender, Utrecht University

Thursday, October 10, 2024 18:00
Amphi 25, Sorbonne University - Faculté des Sciences

Parameterized Algorithms and Complexity Classes

Hans Bodlaender is a full professor in the area of Algorithms and Complexity at Utrecht University, the Netherlands. His work focuses on parameterized algorithms and complexity, and algorithms for graphs and networks. Much of his work was on width parameters for graphs, in particular on the notion of treewidth. He received in 2014 and in 2024 the EATCS-IPEC Nerode Prize, and in 2024 the WG Test-of-Time award.

Many computationally hard problems become easier when some aspect of the input or requested answer is small. In the field of parameterized algorithms, the complexity of computational problems is studied under the lens where a parameter in the input is considered significantly smaller than the input size. In this talk, some of the main concepts of the field are surveyed with the help of a number of examples, including the notions of fixed parameter tractability (FPT algorithms), the W-hierarchy, slicewise polynomial time (XP), kernelization, and polynomial kernels. In the second half of the talk, some recent developments are discussed: many problems that have been shown to be solvable in slicewise polynomial time (are in XP) by using dynamic programming can be shown to be complete for the newly discovered complexity classes XNLP or XALP. We look at a number of examples from the fields of logic, algorithmic graph theory, and scheduling. The completeness has consequences for the expected use of memory of algorithms for these problems.

Electronic access

• Slides

• Offline video