Module Number INFO4413 
Module Title Parameterized Algorithms 
Lecture Type(s) Lecture 

ECTS  6  
Work load  Contact time  Self study 
Workload:
180 h Class time:
60 h / 4 SWS Self study:
120 h 

Duration  1 Semester  
Frequency  Irregular  
Language of instruction  German and English  
Type of Exam  Written exam (in case of a small number of participants: oral tests) 

Content  This module gives an introduction to the theory of parameterized algorithms and parameterized complexity theory. The focus is on different methods and techniques for developing parameterized algorithms. This module introduces solution approaches to NP complete problems, parameterized algorithms, and problem kernels. Different methods and techniques, such as data reduction and problem kernels, depthconstrained search trees, dynamic programming, tree decompositions, iterative compression, color coding, and linear programming, are introduced. From the area of parametrized complexity theory, parametrized reduction, the class FPT and Hardness classes are treated. 

Objectives  Students have basic knowledge of parameterised algorithms and parameterised complexity and can assess and determine the difficulty of NPcomplete problems and algorithms for solving them exactly. They know different methods and techniques for designing parameterised algorithms. They can solve different problems with the repertoire of methods presented as well as creatively develop parameterised algorithms independently. The students can distinguish between different strategies for the design of parameterised algorithms and apply these adapted to the problem. The students are able to critically evaluate a parameterised algorithm. They recognise advantages and disadvantages of this approach and can place it in the context of other methods for solving NPcomplete problems such as heuristics, approximation algorithms, randomised algorithms. 

Allocation of credits / grading 
Type of Class
Status
SWS
Credits
Type of Exam
Exam duration
Evaluation
Calculation
of Module (%)
Lecture
V
o
3
4.5
wt
90
g
100
Tutorial
Ü
o
1
1.5


Prerequisite for participation  There are no specific prerequisites.  
Lecturer / Other  Dorn  
Literature  Rolf Niedermeier: Invitation to FixedParameter Algorithms, Oxford University Press. 

Last offered    
Planned for    
Assigned Study Areas  INFOINFO, INFOTHEO, MEDIAPPL, MEDIINFO, MLCS 