Parameterized Complexity

term paper


In parameterized complexity the focus is on the question: What makes the problem computationally difficult? — Downey and Fellows (1999)

Parameterized complexity is a very young and active direction of research. It takes a multi dimensional point of view on the problem. Not only the instance size but also other structural parameters matter. It can be used to find out, where the hardness of a problem yields from. It also narrows the gap between theory an practice. On the one hand it can give us proofs why certain approaches work in practice. On the other hand, and even more important, it can provide new, exact algorithms for hard problems. In the future we will see many more applications of the results from parameterized complexity.

This is a subject that every computer scientist should know about. — Foinn Murtagh, Editor-in-Chief of The Computer Journal