Parametrisierte Algorithmen

Lecturer: Thomas Bläsius

Teaching Assistants: Jean-Pierre von der Heydt, Elly Schmidt, Wendy Yi

Many algorithmic problems appearing in applications are NP-hard. This means that there are no algorithms that efficiently solve these problems on every input (assuming P ≠ NP). Nonetheless, one can often solve these problems efficiently if the inputs are in some sense well-behaved. The parameterized complexity provides a way to formalize the concept of well-behaved inputs. This is done by associating with every input a parameter k, which represents a measure for the complexity of the input. Then the goal is to find an algorithms with running time polynomial in the input size, while allowing it to be exponential (or worse) in the parameter k. Compared to the coarse classification of problems in to polynomially solvable or NP-hard, this provides a more nuanced perspective on the computational complexity of problems.