Fine-grained Parameterized Algorithms

• Course codes: M-AfgD-12-K→FPA12
• External links: qis

Overview

Inhalt

Diese Vorlesung behandelt aktuelle Forschungsthemen aus der theoretischen Informatik und richtet sich an Student:innen, die Algorithmen und theoretische Informatik gut finden. Es werden etwa hälftig algorithmische und komplexitätstheoretische Fragen und Ergebnisse abgedeckt. Vorrausgesetzt werden Grundbegriffe aus Algorithmen und Datenstrukturen sowie Grundwissen in diskreter Mathematik. Komplexitätstheorie und algorithmische Vertiefungsvorlesungen sind von Vorteil, werden aber nicht formal vorausgesetzt.

Vorlesungsmaterial

In Teil 1 folgen wir diesem Buch:

• CFKLMPPS: Parameterized Algorithms von Cygan, Fomin, Kowalik, et al. [pdf · UB · e-UB]

Hier ist der (vorläufige) Plan:

• Woche 1 (Nov 2-6):

  • [video] [Kapitel 1, 2.2.1, 3.1, 3.2] Vertex-Cover: Reduktionsregeln, $O(k^2)$-Kernelisierung, einfache Branching-Algorithmen
  • [video] [Kapitel 1, 2.1] Grundlegende Definitionen, Äquivalenz von Kernelisierung und FPT
  • [video] [Kapitel 2.2.3, 2.3, 2.5] Kernelisierung von Edge Clique Cover, Crown Reduktion für Vertex-Cover, Kernels via Lineare Programmierung
  • [pdf] Erstes Übungsblatt (bitte ignorieren Sie organisatorische Anmerkungen auf dem Blatt, es stammt aus einer alten Iteration). Sie werden die Lösungen nächste Woche in der Übungsgruppe vorstellen.

• Woche 2 (Nov 9-13):

  • [video] [3.1, 3.4] Bounded Search Trees (Vertex Cover Above LP)
  • [video] [4.1, 4.3.1] Iterative Kompression (Vertex Cover, Feedback Vertex Set)
  • [video] [5.1, 5.2] Randomisierte Algorithmen (Feedback Vertex Set, Color-coding)
  • Übungen: Aufgaben 2.1, 2.2, 2.3 von Blatt 2 [pdf] und Aufgaben 3.1, 3.3, 3.4 von Blatt 3 [pdf]. Die Lösungen werden am 20.11. besprochen.

• Woche 3 (Nov 16-20):

  • [video 6 min] Überblick über die Themen der Woche
  • [video 39 min] [7.1] Dynamische Programmierung (auf Bäumen, schmalen Gittern)
  • [video 44 min] [7.2] Pfadweite (Definition, Separationseigenschaft, nette Pfadzerlegungen)
  • [video 19 min] [7.2] Baumweite (Definition, Separationseigenschaft, nette Baumzerlegungen)
  • [video 35 min] [7.3.1] Dynamische Programmierung auf Graphen beschränkter Baumweite
  • [video 35 min] [7.4] Satz von Courcelle
  • Alle Übungsaufgaben auf “Problem set 5” [pdf]. Die Lösungen werden erst nächste Woche besprochen.
  • Übungsgruppe am 20.11.: Wir besprechen die Lösungen der Aufgaben aus Wochen 1 und 2.

• Woche 4 (Nov 23-27):

  • [video 6 min] Überblick über die Themen der Woche
  • [video 45 min] [7.6] Berechnung von Baumweite, Lemmas zu Balancierte Separatoren
  • [video 12 min] [7.6] Korollar 7.21
  • [video 52 min] [7.6] Baumweite berechnen: Algorithmus und Korrektheitsbeweis
  • [video 11 min] Cops and Robber [7.5]
  • [video 26 min] Graphminoren [6.3], Ausgeschlossene Minoren und Gitter [7.7]
  • [video 14 min] Win/Win-Algorithmen und Bidimensionalität [7.7]
  • Übungsaufgaben 7.35, 7.37, 7.40, 7.54 im Buch. Diese Aufgaben werden erst nächste Woche besprochen.
  • Übungsgruppe am 27.11.: Wir besprechen die Lösungen der Aufgaben aus Woche 3.

• Woche 5 (Nov 30 - Dec 4): Algebraische Methoden

  • [video 3 min] Überblick über die Themen der Woche
  • [video 16 min] Methode: Das Prinzip von Inklusion und Exklusion [10.1]
  • [video 20 min] Beispiel: Hamiltonkreise zählen mit Inklusion-Exklusion [10.1.1]
  • [video 41 min] Beispiel: Steinerbäume finden mit Inklusion-Exklusion [10.1.2]
  • [video 27 min] Methode: Schnelle Möbius Transformation [10.2]
  • [video 29 min] Methode: Schnelle Teilmengenfaltung, echte Färbungen zählen [10.3, 10.3.1]
  • Übungsaufgaben: Aufgaben 10.6 und 10.9 im Buch, für Mutige auch Problem 7.4 auf diesem Übungsblatt [pdf].
  • Übungsgruppe am 4.12..

• Woche 6 (Dec 7-11):

  • [todo] Überblick über die Themen der Woche
  • [video 84 min] $k$-Pfade in Zeit $O(2^k)$ finden [10.4]
  • Übungsaufgabe: 10.19 im Buch.
  • Übungsgruppe am 11.12.: Wir besprechen die Lösungen der Blattaufgabe 3.4 aus Woche 2, Blattaufgabe 5.4 aus Woche 3, und die Buchaufgaben der Woche 4.

• Woche 7 (Dec 14-18): Fixed-Parameter Intractability

  • [video 21 min] Parameterized reductions 13.1
  • [video 12 min] Clique, Independent Set, Vertex Cover 13.1
  • [video 37 min] Multicolored Clique and Friends 13.2
  • [video 15 min] Dominating Set and Friends 13.2
  • [video 24 min] W-Hierarchy 13.3
  • Übungsaufgaben: 13.1, 13.2, 13.23
  • Übungsgruppe am 18.12.: Wir besprechen die Lösungen der Aufgaben aus Woche 5 und Woche 6.

In Teil 2 folgen wir in wesentlichen Teilen der Vorlesung von Bringmann/Künnemann (henceforth refered to as BK).

• Woche 8 & 9 (Jan 18-29): Introduction to Fine-grained complexity

  • [video 5 min] Introduction
  • [video 45 min] [lecture notes] Schoening’s Algorithm for k-CNF-SAT
  • [video 16 min] Strong Exponential Time Hypothesis (SETH)
  • [video 14 min] The Orthogonal Vector Problem
  • [video 25 min]: new Reduction from CNF-SAT to OV
  • please read BK, chapter 1 and BK, chapter 2
  • Exercises: Exercises 1 and 2a from ex00.pdf and Exercises 1, 2b, 4 from ex01.pdf
  • Übungsgruppe am 22.01. und 28.01.: Wir besprechen Übungsaufgaben und Fragen.

• Woche 10 (Feb 1-5): The Polynomial Method

  • [video 19 min] Ziel: Subquadratischer Algorithmus für OV wenn $d=O(\log n)$.
  • [video 10 min] Schnelle Multiplikation von Rechtecksmatrizen
  • [video 20 min] Schnelle Evaluation von Multivariaten Polynomen
  • [video 10 min] Boolsche Formel für OV wird übersetzt in Arithmetische Formel
  • [video 37 min] Probabilistische Polynome, Satz von Razborov und Smolensky
  • [video 19 min] Probabilistisches Polynom für OV
  • [video 28 min] Zusammenfassung, Gesamtalgorithmus, Korrektheit, Laufzeit
  • please read BK, chapter 4
  • Exercises: Exercise 1 and 2 from ex02.pdf
  • Übungsgruppe am 03.02. um 12:30: Wir besprechen Übungsaufgaben und Fragen.
  • Übungsgruppe am 05.02.: Wir besprechen Übungsaufgaben und Fragen.

• Woche 11 (Feb 8-12): The Polynomial Method for APSP

  • please read BK, chapter 5
  • Exercises: Exercise 3 and 5 from ex03.pdf
  • Übungsgruppe am 11.02.: Wir besprechen Übungsaufgaben und Fragen.

• Woche 12 (Feb 15-19): Review of the semester

  • Zwei Videositzungen (je 1h, Termin wird noch gefunden), in denen wir Themen des Semesters wiederholen:
    • Parameterized algorithms
    • Fine-grained complexity
  • Übungsgruppe am 18.02.: Wir besprechen noch offene Übungsaufgaben und Fragen.

Weitere Details:

• Für welche Module Sie diese Veranstaltung einbringen können, können Sie im qis nachlesen.
• Die Vorlesungen finden online statt. Der Termin ist Di-Mi 14-16.
• Die Übungen finden Fr 10-12 online statt. Jede Woche gibt es Übungen, deren Lösungen in der Übungsgruppe besprochen werden.
• Die mündliche Prüfung findet am 25.02.2021 (+/- ein Tag) statt, Termine werden einzeln vereinbart.
• Zeitaufwand: 10 ECTS mit je 25h = 250h. Mit 50 Stunden Klausurvorbereitung landen wir bei 200h/14 = 14h pro Woche. Davon sind 4h Vorlesung, 2h Übungsgruppe und 8h Übungsaufgaben+Vorlesungsnachbereitung.

Inhalt

In dieser Vorlesung geht es um schnelle Algorithmen für “schwere” Berechnungsprobleme und immer auch um die Frage, ob noch schnellere Algorithmen möglich sind. Der Ausgangspunkt ist die Beobachtung, dass NP-Vollständigkeit und die Klassifikation von Problemen in Polynomialzeit und NP-schwer oft zu grobkörnig ist, um genaue Aussagen über die bestmöglich Laufzeit zu erzielen.

Wenn ein Algorithmus in Zeit $O(n^3)$ läuft, ist dennoch von höchstem Interesse, ob es nicht einen cleveren und noch unbekannten Algorithmus geben könnte, der nur Zeit $O(n^{2.99})$ oder $O(n)$ braucht. Und nur weil ein Problem NP-schwer ist und damit keinen Polynomialzeitalgorithmus hat, heißt das noch lange nicht, dass man das Problem nicht gelöst haben möchte. Daher ist die Frage interessant, wie schnell man das Problem denn nun lösen kann: Vielleicht in Zeit $O(n^n)$, $O(2^n)$ oder gar $O(1.3^k n)$ wo $k$ ein weiterer Parameter der Eingabe ist?

Dieser Kurs vermittelt spannende algorithmische Techniken, um die Komplexität von NP-schweren und Polynomialzeitproblemen genauer zu analysieren. Die Übungen bilden einen wichtigen Teil der Veranstaltung: Darin werden Sie algorithmische Techniken selbständig anwenden und auch Komplexitätsannahmen benutzen, um zu zeigen, dass bestimmte Probleme keine schnelleren Algorithmen zulassen.

Lernziele

Nach der Veranstaltung kann der:die Student:in

• verschiedene Komplexitätsannahmen aus dem Gebiet der parametrisierten und feinkörnigen Komplexität nennen und miteinander vergleichen,
• wichtige Ergebnisse, Algorithmen und Beweistechniken aus dem Gebiet reproduzieren und auf ähnliche Probleme übertragen,
• die Möglichkeiten und Grenzen der Methoden des Gebiets einschätzen.

Literatur und Links

• Cygan et al. “Parameterized Algorithms” [preprint pdf • e-UB • ISBN 978-3-319-21274-6].
• Eine vorherige Iteration dieses Kurses: Multivariate Algorithmics (2018).
• Vorlesungsskript der Vorlesung von Bringmann and Künnemann an der Universität des Saarlandes [url]
• Diverse wissenschaftliche Publikationen aus dem Gebiet.

Weitere Literatur:

• Flum and Grohe “Parameterized Complexity Theory”
• Downey and Fellows “Fundamentals of Parameterized Complexity”
• Parameterized complexity course von Dániel Marx und Pranabendu Misra. (Mit Videos und Folien)