Skip to main content

Summer 2022

Parametrisierte Komplexität
Parameterized Complexity

03-ME-602.22 (03-IMAT-PK)

Vorlesung
ECTS: 6

Termine:
wöchentlich Mo 10:00 - 12:00 MZH 3150 Vorlesung Präsenz
wöchentlich Mi 10:00 - 12:00 MZH 3150 Übung Präsenz

Profil: SQ
Schwerpunkt: SQ

 

Die parametrisierte Komplexitätstheorie ist ein relativ junges Teilgebiet der theoretischen Informatik. In der klassischen Komplexitätstheorie werden Laufzeiten von Algorithmen bezüglich der Eingabelänge n gemessen. In der parametrisierten Komplexitätstheorie wird eine feinere Analyse angewendet und Laufzeiten bezüglich einem oder mehreren zusätzlichen Parametern beschrieben. So können in vielen Fällen Algorithmen entwickelt werden, die selbst für NP-schwere Probleme auf Instanzen mit kleinen Parametern effizient sind. Insbesondere sind Instanzen, die in der Praxis auftreten, häufig strukturell einfach. Die parametrisierte Komplexitätstheorie kann in diesen Fällen erklären, warum NP-schwere Probleme in der Praxis häufig schnell gelöst werden können. In dieser Vorlesung lernen wir viele Techniken zum Entwurf effizienter parametrisierter Algorithmen kennen. 

 

Inhalte. 

1. Motivation

2. FPT und XP

3. Kernelization und Äquivalenz zu FPT

4. Crown Decompositions und Vertex Cover

5. Sunflower Lemma und Hitting sets

6. Lineare Programmierung für Vertex Cover

7. Bounded Search Trees

8. Feedback Vertex Set

9. Above Guarantee Parameterizations

10. Iterative Kompression und Odd Cycle Transversal

11. Dynamische Programmierung über Baumzerlegungen

(11b. Color Coding)

12. Beyond FPT: die W-Hierarchie

13. Die Exponential Time Hypothesis (ETH) in der parametrisierten Welt

14. FPT und Approximation

Projekt GraPA
(WiSe 21/22 bis SoSe 2022)
03-IMPJ-GRAPA


Projektplenum
ECTS: 12

Termine:
wöchentlich Fr 08:00 - 10:00 MZH 3150 Plenum Präsenz

 

Sparsity - Graphs and algorithms (in englischer Sprache)

03-ME-602.21 (03-IMVT-SGA)

Vorlesung
ECTS: 6

Termine:
wöchentlich Di 08:00 - 10:00 MZH 3150 Übung Präsenz
wöchentlich Do 10:00 - 12:00 MZH 3150 Vorlesung Präsenz

Profil: SQ

Kombinatorik (Seminar)

03-ME-602.23 (03-IMS-KOMB)

Seminar
ECTS: 3

Termine:
wöchentlich Di 12:00 - 14:00 MZH 3150 Seminar Präsenz

Profil: SQ