Computational Complexity

Computational Complexity

Modern algorithm theory gives us a variety of tools to obtain insight in what efficiency is possible to achieve for specific problems. A complexity theoretic study of a problem can go hand in hand with the design and analysis of algorithms for it, to precise establish this possible efficiency, the computational complexity of the problem. An important direction in this research is the fixed parameter complexity of a problem, where we analyze algorithmic problems for the case that a certain parameter (e.g., the size of the desired solution) is small. Kernelization algorithms yields us problems that are fixed parameter tractable (FPT), but also is an important tool to analyze the preprocessing of combinatorial problems.