Anmeldung

Sie können sich bis zum 7. Februar per Email an seminar [AT] logic.rwth-aachen.de für das Seminar anmelden. Bitte geben Sie dazu Ihren vollständigen Namen, Matrikelnummer, Studiengang, Fachsemester und Ihre Vorkenntnisse (insbesondere an unserem Lehrgebiet besuchte Vorlesungen) an.

Kurzentschlossene, die sich vor dem 14. Januar anmelden, werden bereits am 15. Januar verständigt, ob sie einen Platz erhalten.

Organisation

Die Veranstaltung wird als Blockseminar am Ende der Vorlesungszeit durchgeführt.

Zeitplan

03.05.	Gliederung
31.05.	Ausarbeitung
14.06.	Endgültige Fassung
21.06.	Folien

Programm

Montag, 19. July
10:00	–	10:45	Mieke Kuschnerus	DAG-Weite
10:50	–	11:35	Katinka Becker	Kelly-Weite
11:40	–	12:25	Nikolai Thiemo Pape	Entanglement

Inhalt

Many graph-theoretic problems that are difficult on general graphs can be easily solved on graphs that are “simple” in a certain sense, e.g., on graphs that resemble trees. There are several measures for simplicity (or complexity) of graphs such as tree width, clique width, entanglement, and DAG width.

Interestingly, many of these measures can be characterised by so-called graph searching games. These are games in which a group of searchers try to capture a fugitive (think of, e.g., the board game “Scotland Yard”). By adjusting the rules of the game, i.e., by specifying how and when the players are allowed to move through the graph, whether the players can see the others' positions or moves, or by requiring the searchers to capture the fugitive in a special way, we obtain a large variety of games, and the number of searchers needed for capturing the fugitive in some graph yields a measure for a certain aspect of its structural complexity.

In this seminar, we will motivate, introduce and compare several graph parameters and investigate the corresponding searching games. Of special interest will be recent research on transferring well-established notions like tree width, which is defined for undirected graphs, to appropriate and useful notions for directed graphs, and further extensions of the concepts to more general classes of structures like hypergraphs or matroids.

Themen

Thema	Vortragende(r)	Betreuer(in)	Literatur
DAG-Weite	Mieke Kuschnerus	R. Rabinovich	[BDHKO10, HPhD (Ch. 6), HK07]
Kelly-Weite	Katinka Becker	D. Fischer	[HK07, HPhD (Ch. 7), MTV07]
Entanglement	Nikolai Thiemo Pape	B. Puchala	[BG04, BPhD (Ch. 4)]

Literatur

[BDHKO10]	D. Berwanger, A. Dawar, P. Hunter, S. Kreutzer, and J. Obdržálek. The DAG-Width of Directed Graphs. 2010.
[BG04]	D. Berwanger and E. Grädel. Entanglement – A Measure for the Complexity of Directed Graphs with Applications to Logic and Games. In Proceedings of LPAR 2004, Montevideo, Uruguay, vol. 3452 of LNCS, pp. 209–223. Springer, 2005.
[BPhD]	D. Berwanger. Games and Logical Expressiveness. PhD thesis, Department of Computer Science, RWTH Aachen, Germany, 2005.
[HK07]	P. Hunter and S. Kreutzer. Digraph measures: Kelly decompositions, games, and orderings. In SODA, pp. 637-644, 2007.
[HPhD]	P. Hunter. Complexity and Infinite Games on Finite Graphs. PhD thesis, Computer Laboratory, University of Cambridge, 2007.
[MTV07]	D. Meister, J. A. Telle, and M. Vatshelle. Characterization and Recognition of Digraphs of Bounded Kelly-width. In WG, pp. 270-279, 2007.

Zuordnung

• Informatik (B.Sc.)/Seminar Informatik
• Mathematik (B.Sc.)/Seminar: Logik, Komplexität, Spiele
• Informatik (D)/Hauptstudium/Theoretische Informatik
• Mathematik (D)/Hauptstudium/Reine Mathematik
• Informatik (S II)
• Mathematik (S II)/Hauptstudium/Modul Angewandte Mathematik

Voraussetzungen

• Modul Mathematische Logik
• für B.Sc. Informatik: bestandenes Modul "Einführung in das wissenschaftliche Arbeiten (Proseminar)"

Rückfragen

Erich Grädel, Diana Fischer, Tobias Ganzow, Łukasz Kaiser, Bernd Puchala, Roman Rabinovich