Logbuch zur Vorlesung Graphzerlegungen in Algorithmik und Logik

Di, 17.4.2007: Übersicht über den Inhalt der Vorlesung. Verschiedene algorithmische Probleme vorgestellt. Parametrische Komplexität. Die Logiken FO und MSO.
Do, 19.4.2007: Kapitel 2. Dynamisches Programmieren auf Bäumen. Algorithmen für das vertex cover und das dominating set Problem. Definition von Baumzerlegungen.
Di, 24.4.2007: Kapitel 2.2. Baumzerlegungen. Definition von BZ, Grundlegende Eigenschaften von Baumzerlegungen, kleine Baumzerlegungen und Separatoren.
Do, 26.4.2007: Weitere Eigenschaften von Baumzerlegungen. Zusammenhang Baumweite und Zahl der Kanten. Algorithmen auf Graphen kleiner BW: Färbbarkeit.
Do, 3.5.2007: Normale Baumzerlegungen. Algorithmen auf Graphen kleiner BW: Hamiltonkreise. BW und Separatoren. Bis Lemma 2.28.
Di, 8.5.2007: Baumweite und Separatoren. Kapitel 2.4. Berechnen von Baumzerlegungen aus Separatoren. Abschluss von Kapitel 2.5.
Do, 10.5.2007: Baumzerlegungen von Strukturen. Baumautomaten, reguläre Baumsprachen, MSO auf Bäumen. Bis Beispiel 2.48.
Di, 15.5.2007: Übersetzung von MSO in Baumautomaten umgekehrt. Leerheitstest für Baumautomaten. Bis Lemma 2.55.
Di, 22.5.2007: MSO auf Graphklassen beschränkter Baumweite. Bis vor Lemma 2.62.
Do, 24.5.2007: Die Sätze von Courcelle und Seese. Minoren. Bis zu Satz 2.74.
Di, 29.5.2007: Abschluss des Kapitels 2. Kapitel 3: Planare Graphen, Definition, grundlegende Eigenschaften, Algorithmen auf planaren Graphen: Independent Set, Dominating Set. Bis Lemma 3.11.
Do, 31.5.2007: Planare Graphen und Baumweite. Abschluss von Lemma 3.11. Untergraphenisomorphie. Abschluss Kapitel 3.2.
Di, 5.6.2007: Abschluss Kapitel 3.3: Auswerten prädikatenlogischer Formeln, Approximationsalgorithmen auf planaren Graphen.
Do, 7.6.2007: Kapitel 4: Lokale Baumweite. Auswerten prädikatenlogischer Formeln, Approximationsalgorithmen. Kapitel 5: Graphklassen mit verbotenen Minoren, Eigenschaften und Beispiele, Wagners Vermutung und Minorentest, Baumzerlegungen über einer Klasse, bis Bemerkung 5.11.
Di, 12.6.2007: Baumzerlegungen über eine Klasse mit fast lokal beschränkter Baumweite, Satz 5.16: Approximation von Min-Vertex-Cover auf Klassen mit verbotenen Minoren.
Do, 14.6.2007: Beweis von Satz 5.16 abgeschlossen. Abschnitt 5.3: Berechenbarkeit verbotener Minoren für beschränkte Baumweite und für die Vereinigung von unter Minoren abgeschlossenen Klassen.
Di, 19.6.2007: Abschnitt 5.4: lokal verbotenen Minoren, Überblick über die Graphklassen und Algorithmen. Kapitel 6: Homomorphismen von Graphen und relationalen Strukturen, Abschnitt 6.3: Constraint-Satisfaction bis zum Beispiel "Ablaufplanung".
Do, 21.6.2007: Konjunktive Anfragen an Datenbanken, Äquivalenz von HOM, CSP und MC(BCQ). Abschnitt 6.3: Einschränkungen von HOM auf der linken Seite, Homomorphieäquivalenz, Kerne, bis Definition 6.25.
Di, 26.6.2007: Kerne, Existenzielles p-Pebble-Spiel, HOM(C) auf Klassen C mit beschränkter Baumweite modulo Homomorphieäquivalenz, bis zum Beweis von Satz 6.32.
Do, 28.6.2007: Parametrische Komplexität, Satz 6.41 über HOM(C) auf unbeschränkter Baumweite modulo Homomorphieäquivalenz, bis Lemma 6.44.
Di, 3.7.2007: Beweis von Satz 6.41 abgeschlossen, beschränkte Stelligkeit ist wesentlich, Kapitel 7: Baumzerlegungen von Hypergraphen, Weitefunktionen, bis Definition 7.8 von "Cover-Baumweite".
Do, 5.7.2007: Cover-Baumweite von Hypergraphen und Strukturen, Beispiele, das Homomorphieproblem auf beschränkter Cover-Baumweite, bis zum Beweis von Lemma 7.17.
Di, 10.7.2007: Das Homomorphieproblem auf beschränkter Cover-Baumweite ist in PTIME
Do, 12.7.2007: Räuber und Gendarmen
Di, 17.7.2007: Sätze 7.29 und 7.30 über Gendarmenweite und Cover-Baumweite, Separatoren für Hypergaphen, bis zum Beweis von Lemma 7.37
Do, 19.7.2007: Kapitel 7 abgeschlossen: Approximation von Cover-Baumweite, das Homomorphieproblem auf beschränkter Cover-Baumweite ohne Zerlegung als Eingabe.

Arbeitsgruppe Logik in der Informatik