Syllabus
- kernelization
- bounded search trees
- iterative compression
- treewidth
- the W-hierarchy
- the exponential-time hypothesis
- parameterized approximation
Annotation
Parameterized algorithmics analyzes the runtime in finer detail than classical complexity theory: instead of expressing the runtime as a function of the input size only, the dependence on a parameter of the input is taken into account. The aim is to isolate any fast growth of the runtime to a parameter, while the remaining growth of the time is kept low.
Apart from giving a deeper theoretical understanding of the complexity of a problem, this can also lead to efficient (practical) algorithms if the parameter describes a property of the inputs, for which the parameter is typically small.