Seminar Logic, Complexity, Games: Algorithmic Meta-Theorems and Parameterized Complexity

WS 2021


Students with a subject in mathematics can apply by writing an email to seminar [AT] including their name, immatriculation no., subject of studies, no. of semesters of studies, and information about relevant modules they have passed (especially lectures from our group).


The presentations will take place as a block seminar at the end of the semester. Presentations may be held in either English or German.
  • Length of seminar papers: 5-6 pages.
  • Duration of presentations: 25 minutes.


16.12.20221. version seminar paper
14.01.2022final version seminar paper


Dienstag, 15. Februar
9:009:30Alexander Salostowitz Fixed-parameter tractability and kernelization
9:3010:00Daniel ZilkenHierarchies in parameterised complexity theory (1)
10:0010:30Jan-Christoph KassingHierarchies in parameterised complexity theory (2)
10:3010:45 Pause
10:4511:15Sven DriessenTree width
11:1511:45Niclas GeyCourcelle's Theorem
11:4512:15Jonathan SchneiderClique width
12:1513:45 Mittagspause
13:4514:15Emil LüpfertVariants of monadic second order logic
14:1514:45Gunnar LüdersFO properties of locally tree-decomposable structures
14:4515:15Lukas PieperLocality of first-order logic and Seese's Theorem


Fixed-parameter tractability and kernelization Alexander SalostowitzBenedikt Pago[FG06, T10 ]
Hierarchies in parameterised complexity theory (1)Daniel Zilken Lovro Mrkonjić[FG06]
Hierarchies in parameterised complexity theory (2)Jan-Christoph Kassing Lovro Mrkonjić[FG06]
Tree widthSven DriessenMatthias Naaf[B96, FG06, ST93]
Courcelle's TheoremNiclas GeyMatthias Naaf[FG06, K09]
Clique widthJonathan SchneiderBenedikt Pago[K09, C00]
Variants of monadic second order logicEmil LüpfertBenedikt Pago[ C96, C03]
FO properties of locally tree-decomposable structuresGunnar LüdersMatthias Naaf[FG01]
Locality of first-order logic and Seese's TheoremLukas PieperLovro Mrkonjić[EF95, S95, K09]


Algorithmic meta-theorems can be seen as a tool to obtain algorithms for a whole class of problems at once. Then, in order to show that a certain problem is algorithmically tractable, it is sufficient to verify that the problem is contained in the class covered by the meta-theorem. A famous example is Courcelle's Theorem: For every fixed sentence of monadic second order logic, there exists a linear-time model checking algorithm for structures of bounded treewidth (roughly speaking, treewidth says how similar a graph is to a tree). This is a meta-theorem because it actually yields an infinite number of algorithms, one for each MSO-sentence. As a consequence of this, many well-known NP-complete problems, such as three-colourability or vertex cover, can be solved efficiently on graphs of bounded treewidth: Simply express the existence of a colouring or a vertex cover as an MSO-sentence, and run the model checking algorithm from Courcelle's theorem. Algorithms like this show that the difficulty of many hard problems depends on structural parameters of the input instance, in this case, how "treelike" the graph is. The area of research that generally analyses the complexity of different problems in dependence of such parameters is parameterized complexity theory. Apart from algorithmic meta-theorems, this seminar will also cover the most important parameterized complexity classes and some of the fundamental techniques for the design of efficient algorithms for parameterized problems.


[B96]H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on computing, vol. 25(6), pp. 1305–1317, 1996.
[C00]B. Courcelle, J. A. Makowsky, and U. Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems, vol. 33(2), pp. 125–150, 2000.
[C03]B. Courcelle. The monadic second-order logic of graphs XIV: Uniformly sparse graphs and edge set quantifications. Theoretical Computer Science, vol. 299(1), pp. 1–36, 2003.
[C96]B. Courcelle. On the Expression of Graph Properties in some Fragments of Monadic Second-Order Logic. Descriptive complexity and finite models, vol. 31, pp. 33–62, 1996.
[EF95]H. Ebbinghaus and J. Flum. Finite model theory. Springer, 1995.
[FG01]M. Frick and M. Grohe. Deciding First-order Properties of Locally Tree-decomposable Structures. J. ACM, vol. 48(6), pp. 1184–1206, 2001.
[FG06]J. Flum and M. Grohe. Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006.
[G08]M. Grohe. Logic, graphs, and algorithms. In Logic and Automata, vol. 2 of Texts in Logic and Games, pp. 357–422. Amsterdam University Press, 2008.
[K09]S. Kreutzer. Algorithmic Meta-Theorems. Electronic Colloquium on Computational Complexity (ECCC), vol. 16, pp. 147, 2009.
[S95]D. Seese. Linear time computable problems and logical descriptions. Electr. Notes Theor. Comput. Sci., vol. 2, pp. 246–259, 1995.
[ST93]P. D. Seymour and R. Thomas. Graph searching and a min-max theorem for tree-width. Journal of Combinatorial Theory, Series B, vol. 58(1), pp. 22–33, 1993.
[T10]S. Thomassé. A 4 k 2 kernel for feedback vertex set. ACM Transactions on Algorithms (TALG), vol. 6(2), pp. 1–8, 2010.


  • Bachelor Informatik
  • Master Informatik
  • Bachelor Lehramt Informatik
  • Master Lehramt Informatik
  • Bachelor Mathematik
  • Master Mathematik


  • Mathematical Logic
  • for B.Sc. Computer Science: Module "Einführung in das wissenschaftliche Arbeiten (Proseminar)"


Erich Grädel, Benedikt Pago, Matthias Naaf, Lovro Mrkonjić, Richard Wilke