After attending this course, students should be familiar with the most common width parameters and some of their applications in AI and database theory. They should also be able to design dynamic programming algorithms for the corresponding decompositions.

Many combinatorial problems that are intractable in general can be efficiently solved on tree-like structures. Width parameters measuring "tree-likeness" and their corresponding decompositions can be used to design algorithms that are fast as long as the width of the input is reasonably small.

The course will cover common graph and hypergraph width parameters and some of their applications in AI and database theory. Specifically, we will discuss the graph measure tree-width and generalizations such as clique-width and rank-width. We then proceed to discuss hypergraph width parameters like hypertree-width and fractional hypertree-width.

We will also showcase applications of width parameters to problems such as propositional model counting, conjunctive query evaluation, and inference in Bayesian Networks.

ECTS Breakdown:

18 h lectures
37 h preparing paper presentation
20 h preparation for final exam
-------------------------------------
75 h total

Grading is based on a presentation of a research paper (65%) and an oral exam (35%).

- Jörg Flum, Martin Grohe: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, Springer 2006.

- Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: Parameterized Algorithms. Springer 2015.

This course requires familiarity with fundamental graph theoretic definitions as well as basic knowledge of algorithmics and complexity theory. Knowledge of the topics covered in the "Algorithmics" course is an advantage.