Selected Topics in Logic and Complexity: Directed Graph Structure Theory

In diesem Kurs stellen wir gerichtete Graphen und die grundlegenden Konzepte, um mit diesen und ihrer Struktur zu arbeiten. Wir betrachten einige klassische Ergebnisse zu Digraphen, wie beispielsweise eine gerichtete Version von Menger's Theorem, aber auch neuere Erkenntnisse, die durch Fortschritte im Verständnis der Struktur ungerichteter Graphen inspiriert wurden, wie beispielsweise die Erdos-Pósa-Eigenschaft gerichteter Kreise. Werkzeuge der Graphstrukturtheorie werden häufig zum Beweis von Dualitäten eingesetzt. Hier geht es darum, entweder zu zeigen, dass der Graph eine Struktur hat, auf der sich algorithmische Probleme effizient lösen lassen, oder einen Teil des Graphen zu finden, der eine gewisse Härte aufweist. In diesem Zusammenhang führen wir Weiteparameter und Einschlussrelationen für gerichtete Graphen ein und lernen ihre algorithmischen Anwendungen kennen. Wir betrachten außerdem einige gerichtete Graphklassen mit eingeschränkter Struktur, wie beispielsweise Eulersche oder planare gerichtete Graphen, und ihre Eigenschaften. Ziel ist es, dass die Studierenden einen Überblick über unser Wissen über gerichtete Graphen erhalten und ein Gefühl für die Grenzen unseres Wissens und die Gründe für ihre Existenz dieser Grenzen entwickeln. Qualifikationen Nach erfolgreichem Abschluss des Moduls sind die Studierenden in der Lage, – grundlegende Kenntnisse im Bereich der gerichteten Graphen(struktur)theorie zu erläutern, – fortgeschrittene Techniken aus verschiedenen Bereichen der theoretischen Informatik (Algorithmik, Komplexitätstheorie) anzuwenden, – fortgeschrittene Werkzeuge der strukturellen Graphentheorie, insbesondere auf Digraphen, anzuwenden, – diese Techniken im Kontext aktueller Forschungsthemen zu kombinieren und anzuwenden.