Seminar Logik, Komplexität, Spiele: Algorithmische Meta-Theoreme und parametrisierte Komplexität

WS 2021

Anmeldung

  • Studierende in Mathematik-Studiengängen können sich per Email an seminar [AT] logic.rwth-aachen.de bewerben. Bitte geben Sie dazu Ihren vollständigen Namen, Matrikelnummer, Studiengang, Fachsemester und Ihre Vorkenntnisse (insbesondere an unserem Lehrgebiet besuchte Vorlesungen) an.
  • Studierende in Informatik-Studiengängen können sich über die zentrale Vergabe von Seminarplätzen bewerben.

Organisation

Die Veranstaltung wird als Blockseminar angeboten. Die Vorträge werden am Ende des Semesters wahlweise auf deutsch oder englisch gehalten.
  • Länge der Ausarbeitung: 5-6 Seiten.
  • Vortragsdauer: 25 Minuten.

Zeitplan

16.12.20221. Version Ausarbeitung
14.01.2022finale Version Ausarbeitung
02.02.2022Folien
15.02.2022Seminar

Ausarbeitungen

Programm

Dienstag, 15. Februar
9:00–9:30Alexander Salostowitz Fixed-parameter tractability und Kernelisierung
9:30–10:00Daniel ZilkenHierarchien in der parametrisierten Komplexitätstheorie (1)
10:00–10:30Jan-Christoph KassingHierarchien in der parametrisierten Komplexitätstheorie (2)
10:30–10:45 Pause
10:45–11:15Sven DriessenBaumweite
11:15–11:45Niclas GeyDer Satz von Courcelle
11:45–12:15Jonathan SchneiderCliquenweite
12:15–13:45 Mittagspause
13:45–14:15Emil LüpfertVarianten von monadischer Logik zweiter Stufe
14:15–14:45Gunnar LüdersFO-Eigenschaften von Strukturen mit lokaler Baumzerlegung
14:45–15:15Lukas PieperLokalität von FO und der Satz von Seese

Themen

ThemaVortragende(r)Betreuer(in)Literatur
Fixed-parameter tractability und Kernelisierung Alexander SalostowitzBenedikt Pago[FG06, T10 ]
Hierarchien in der parametrisierten Komplexitätstheorie (1)Daniel Zilken Lovro Mrkonjić[FG06]
Hierarchien in der parametrisierten Komplexitätstheorie (2)Jan-Christoph Kassing Lovro Mrkonjić[FG06]
BaumweiteSven DriessenMatthias Naaf[B96, FG06, ST93]
Der Satz von CourcelleNiclas GeyMatthias Naaf[FG06, K09]
CliquenweiteJonathan SchneiderBenedikt Pago[K09, C00]
Varianten von monadischer Logik zweiter StufeEmil LüpfertBenedikt Pago[ C96, C03]
FO-Eigenschaften von Strukturen mit lokaler BaumzerlegungGunnar LüdersMatthias Naaf[FG01]
Lokalität von FO und der Satz von SeeseLukas PieperLovro Mrkonjić[EF95, S95, K09]

Inhalt

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.

Literatur

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

Zuordnung

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

Voraussetzungen

  • Mathematische Logik
  • für B.Sc. Informatik: bestandenes Modul "Einführung in das wissenschaftliche Arbeiten (Proseminar)"

Rückfragen

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