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.rwthaachen.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  DAGWeite 

– 

Katinka Becker  KellyWeite 

– 

Nikolai Thiemo Pape  Entanglement 
Content
Many graphtheoretic 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 socalled 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 wellestablished 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 
DAGWeite  Mieke Kuschnerus  R. Rabinovich  [BDHKO10, HPhD (Ch. 6), HK07] 
KellyWeite  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 DAGWidth 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. 637644, 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 Kellywidth. In WG, pp. 270279, 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