Seminar Logic, Complexity, Games: Structural Complexity of Graphs and Graph Searching Games
SS 2010
Registration
Deadline: February 7.
Please write an email to seminar [AT] logic.rwth-aachen.de including your name, immatriculation no., subject of studies, no. of semesters of studies, and information about relevant modules you have passed (especially lectures from our group).
If you apply before January 14, we will confirm acceptance by January 15.
Organisation
The talks are given at the end of the semester in a block of 2 or 3 days.
Deadlines
| 03.05. | Gliederung |
| 31.05. | Ausarbeitung |
| 14.06. | Endgültige Fassung |
| 21.06. | Folien |
Schedule
| Montag, 19. July | ||||
|
|
– |
|
Mieke Kuschnerus | DAG-Weite |
|
|
– |
|
Katinka Becker | Kelly-Weite |
|
|
– |
|
Nikolai Thiemo Pape | Entanglement |
Content
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.
Topics
| 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)] |
Literature
| [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. |
Classification
- 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
Prerequisites
- Module Mathematical Logic
- for B.Sc. Computer Science: Module "Einführung in das wissenschaftliche Arbeiten (Proseminar)"
Contact
Erich Grädel, Diana Fischer, Tobias Ganzow, Łukasz Kaiser, Bernd Puchala, Roman Rabinovich