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

## WS 2021

### Registration

Students with a subject in mathematics can apply by writing an email to seminar [AT] logic.rwth-aachen.de 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).

### Organisation

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.2022 1. version seminar paper 14.01.2022 final version seminar paper 02.02.2022 Slides 15.02.2022 Seminar

### Topics

 Thema Vortragende(r) Betreuer(in) Literatur Fixed-parameter tractability and kernelization Alexander Salostowitz Benedikt 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 width Sven Driessen Matthias Naaf [B96, FG06, ST93] Courcelle's Theorem Niclas Gey Matthias Naaf [FG06, K09] Clique width Jonathan Schneider Benedikt Pago [K09, C00] Variants of monadic second order logic Emil Lüpfert Benedikt Pago [ C96, C03] FO properties of locally tree-decomposable structures Gunnar Lüders Matthias Naaf [FG01] Locality of first-order logic and Seese's Theorem Lukas Pieper Lovro Mrkonjić [EF95, S95, K09]

### Content

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.

### Literature

 [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.

### Classification

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

### Prerequisites

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

### Contact

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