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

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.
[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.
[FG04]M. Frick and M. Grohe. The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic, vol. 130(1-3), pp. 3–31, 2004.
[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.
[GHO00]E. Grädel, C. Hirsch, and M. Otto. Back and Forth Between Guarded and Modal Logics. ACM Transactions on Computational Logics, vol. 3(3), pp. 418 – 463, 2002.
[GK11]M. Grohe and S. Kreutzer. Methods for algorithmic meta theorems. Model Theoretic Methods in Finite Combinatorics, vol. 558, pp. 181–206, 2011.
[GKS14]M. Grohe, S. Kreutzer, and S. Siebertz. Deciding first-order properties of nowhere dense graphs. In STOC, pp. 89–98. ACM, 2014.
[K09]S. Kreutzer. Algorithmic Meta-Theorems. Electronic Colloquium on Computational Complexity (ECCC), vol. 16, pp. 147, 2009.
[S16]S. Siebertz. Nowhere dense classes of graphs. PhD thesis, 2016.
[S95]D. Seese. Linear time computable problems and logical descriptions. Electr. Notes Theor. Comput. Sci., vol. 2, pp. 246–259, 1995.
[Z16]F. A. Zaid. Algorithmic Solutions via Model Theoretic Interpretations. PhD thesis, 2016.

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