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.

Deadlines

16.12.2022	1. version seminar paper
14.01.2022	final version seminar paper
02.02.2022	Slides
15.02.2022	Seminar

Schedule

Dienstag, 15. Februar
9:00	–	9:30	Alexander Salostowitz	Fixed-parameter tractability and kernelization
9:30	–	10:00	Daniel Zilken	Hierarchies in parameterised complexity theory (1)
10:00	–	10:30	Jan-Christoph Kassing	Hierarchies in parameterised complexity theory (2)
10:30	–	10:45	Pause
10:45	–	11:15	Sven Driessen	Tree width
11:15	–	11:45	Niclas Gey	Courcelle's Theorem
11:45	–	12:15	Jonathan Schneider	Clique width
12:15	–	13:45	Mittagspause
13:45	–	14:15	Emil Lüpfert	Variants of monadic second order logic
14:15	–	14:45	Gunnar Lüders	FO properties of locally tree-decomposable structures
14:45	–	15:15	Lukas Pieper	Locality of first-order logic and Seese's Theorem

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