Module Number

INFO-4417
Module Title

Parameterized Algorithms and Complexity
Lecture Type(s)

Lecture, Tutorial
ECTS 9
Work load
- Contact time
- Self study
Workload:
270 h
Class time:
90 h / 6 SWS
Self study:
180 h
Duration 1 Semester
Frequency Irregular
Language of instruction German
Type of Exam

Written exam (in case of a small number of participants: oral tests)

Content

This module gives an extended 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, depth-constrained 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. In addition, issues and trends of current research as well as applications in various fields such as bioinformatics, artificial intelligence, or Computational Social Choice are presented.

Objectives

Students have basic knowledge of parameterised algorithms and parameterised complexity and can assess and determine the difficulty of NP-complete 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. They are able to critically evaluate a parameterised algorithm. They recognise advantages and disadvantages of this approach and can classify it in the context of other methods for solving NP-complete problems such as heuristics, approximation algorithms, randomised algorithms. In addition, the students are familiar with issues of current research and know application examples and case studies.

Allocation of credits / grading
Type of Class
Status
SWS
Credits
Type of Exam
Exam duration
Evaluation
Calculation
of Module (%)
Lecture
V
o
4
6.0
wt
90
g
100
Tutorial
Ü
o
2
3.0
Prerequisite for participation There are no specific prerequisites.
Lecturer / Other Dorn
Literature

Rolf Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.
Rodney G. Downey, Michael R. Fellows: Parameterized Complexity, Springer-Verlag, 1999.
Jörg Flum, Martin Grohe: Parameterized Complexity Theory, Springer-Verlag, 2006.

Last offered ---
Planned for ---
Assigned Study Areas INFO-INFO, INFO-THEO, MEDI-APPL, MEDI-INFO, ML-CS