# 192.135 Fixed-Parameter Algorithms and Complexity Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_21",{id:"j_id_21",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_23",{id:"j_id_23",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});}); 2024W 2023W 2022W

2022W, VU, 3.0h, 4.5EC

## Merkmale

• Semesterwochenstunden: 3.0
• ECTS: 4.5
• Typ: VU Vorlesung mit Übung
• Format der Abhaltung: Präsenz

## Lernergebnisse

Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage...

After successful completion of the course, students will be 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.

## Inhalt der Lehrveranstaltung

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.

## Methoden

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.

## Prüfungsmodus

Schriftlich und Mündlich

## Weitere Informationen

The course will be held in on-site blocked format if possible, and online blocked format otherwise. There will be six lecture blocks, and one additional exercise block.

## LVA Termine

TagZeitDatumOrtBeschreibung
Mo.13:00 - 16:3009.01.2023 - 23.01.2023Seminarraum FAV EG C (Seminarraum Gödel) Lectures
Do.13:00 - 16:3012.01.2023 - 26.01.2023Seminarraum FAV EG C (Seminarraum Gödel) Lectures
Mo.13:00 - 16:3030.01.2023Seminarraum FAV EG C (Seminarraum Gödel) Exercises and Recap
Fixed-Parameter Algorithms and Complexity - Einzeltermine
TagDatumZeitOrtBeschreibung
Mo.09.01.202313:00 - 16:30Seminarraum FAV EG C (Seminarraum Gödel) Lectures
Do.12.01.202313:00 - 16:30Seminarraum FAV EG C (Seminarraum Gödel) Lectures
Mo.16.01.202313:00 - 16:30Seminarraum FAV EG C (Seminarraum Gödel) Lectures
Do.19.01.202313:00 - 16:30Seminarraum FAV EG C (Seminarraum Gödel) Lectures
Mo.23.01.202313:00 - 16:30Seminarraum FAV EG C (Seminarraum Gödel) Lectures
Do.26.01.202313:00 - 16:30Seminarraum FAV EG C (Seminarraum Gödel) Lectures
Mo.30.01.202313:00 - 16:30Seminarraum FAV EG C (Seminarraum Gödel) Exercises and Recap

## Leistungsnachweis

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.

## LVA-Anmeldung

Von Bis Abmeldung bis
17.10.2022 01:00 10.01.2023 23:59

## Curricula

StudienkennzahlVerbindlichkeitSemesterAnm.Bed.Info
066 011 DDP Computational Logic (Erasmus-Mundus) Gebundenes Wahlfach
066 645 Data Science Keine Angabe
066 926 Business Informatics Keine Angabe
066 931 Logic and Computation Gebundenes Wahlfach
066 937 Software Engineering & Internet Computing Gebundenes Wahlfach
066 938 Technische Informatik Gebundenes Wahlfach

## Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

## Vorkenntnisse

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.

Englisch