186.855 Fixed-Parameter Algorithms and Complexity
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2019W, VU, 2.0h, 3.0EC, to be held in blocked form
This course is evaluated following the new mode. Learn more

Course evaluation

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VU Lecture and Exercise

Learning outcomes

After successful completion of the course, students are able to understand the theory of parameterized complexity and fixed-parameter tractability in sufficient depth to read and follow latest developments in the area and, crucially, to analyze problems they encounter from the parameterized viewpoint. First and foremost, this includes the ability to obtain asymptotically efficient algorithms and strong lower bounds for problems of interest.

Subject of course

Fixed-parameter algorithms provide a powerful approach for efficiently solving many NP-hard problems by exploiting structural aspects of problem instances in terms of a problem parameter. This course provides an overview of the main techniques for developing fixed-parameter algorithms (including bounded search trees, kernelization, color coding, modulators) as well as the fundamentals of parameterized complexity theory (such as the Weft-hierarchy, XP and para-NP-hardness, kernelization lower bounds) which allows to provide strong evidence that certain problems cannot be solved by a fixed-parameter algorithm.

Teaching methods

The core of the course consists of a series of blocked lectures which explore advanced topics in the studied area. The lectures are held in an informal, seminar-like setting and are highly interactive - students are expected to actively engage in what's going on. Every new method and technique introduced during the lecture is demonstrated on several examples.

Mode of examination

Written and oral

Additional information

The course information meeting and first lecture start on Thursday 9 January at 14:00 in the Godel seminar room (FAV EG C).

The course will be held blocked in January 2020. Lectures will take place:

  • on three consecutive Thursdays (9.1., 16.1., 23.1.) from 14:00 to 18:00,
  • on three consecutive Mondays (13.1., 20.1., 27.1.) from 12:00 to 16:00. Due to the Algorithmics Exam, on Monday 20.1. the course on that day will be shifted to the time slot 14:00-18:00.

There will be a break in the middle of each block (specific timing is up for discussion).

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Thu14:00 - 18:0009.01.2020 - 23.01.2020Seminarraum FAV EG C (Seminarraum Gödel) Lecture
Mon12:00 - 16:0013.01.2020 - 27.01.2020Seminarraum FAV EG B (Seminarraum von Neumann) Lecture
Tue11:00 - 15:0014.01.2020 - 21.01.2020Seminarraum FAV EG C (Seminarraum Gödel) Fixed-Parameter Algorithms and Complexity (Presentations + Backup)
Mon16:00 - 18:0020.01.2020Seminarraum FAV EG B (Seminarraum von Neumann) Extra lecture
Fixed-Parameter Algorithms and Complexity - Single appointments
DayDateTimeLocationDescription
Thu09.01.202014:00 - 18:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture
Mon13.01.202012:00 - 16:00Seminarraum FAV EG B (Seminarraum von Neumann) Lecture
Tue14.01.202011:00 - 15:00Seminarraum FAV EG C (Seminarraum Gödel) Fixed-Parameter Algorithms and Complexity (Presentations + Backup)
Thu16.01.202014:00 - 18:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture
Mon20.01.202012:00 - 16:00Seminarraum FAV EG B (Seminarraum von Neumann) Lecture
Mon20.01.202016:00 - 18:00Seminarraum FAV EG B (Seminarraum von Neumann) Extra lecture
Tue21.01.202011:00 - 15:00Seminarraum FAV EG C (Seminarraum Gödel) Fixed-Parameter Algorithms and Complexity (Presentations + Backup)
Thu23.01.202014:00 - 18:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture
Mon27.01.202012:00 - 16:00Seminarraum FAV EG B (Seminarraum von Neumann) Lecture
Course is held blocked

Examination modalities

The grading is based on a two-step evaluation process. In the first and mandatory part, each student is expected to select a recent research paper (based on guidance from the lecturer) from the considered area, read it, and prepare a presentation of its contents. This is sufficient to pass the course with a basic grade. Students who want a good grade take an oral exam where they demonstrate their understanding of the topics covered in the lecture.

Course registration

Begin End Deregistration end
09.01.2020 00:01 16.01.2020 23:59 16.01.2020 23:59

Curricula

Literature

No lecture notes are available.

Previous knowledge

This course requires basic knowledge on the design and analysis of algorithms as well as basic complexity theory. Knowledge of the topics covered in the Algorithmics course is an advantage.

Preceding courses

Language

English