New Horizons in Parameterized Complexity (Dagstuhl Seminar 19041)

This report documents the program and the outcomes of Dagstuhl Seminar 19041 "New Horizons in Parameterized Complexity". Parameterized Complexity is celebrating its 30th birthday in 2019. In these three decades, there has been tremendous progress in developing the area. The central vision of Parameterized Complexity through all these years has been to provide the algorithmic and complexity-theoretic toolkit for studying multivariate algorithmics in different disciplines and subfields of Computer Science. These tools are universal as they did not only help in the development of the core of Parameterized Complexity, but also led to its success in other subfields of Computer Science such as Approximation Algorithms, Computational Social Choice, Computational Geometry, problems solvable in P (polynomial time), to name a few. In the last few years, we have witnessed several exciting developments of new parameterized techniques and tools in the following subfields of Computer Science and Optimization: Mathematical Programming, Computational Linear Algebra, Computational Counting, Derandomization, and Approximation Algorithms. The main objective of the seminar was to initiate the discussion on which of the recent domain-specific algorithms and complexity advances can become useful in other domains