Algomanet - fall 2024

Basic information

The two Algomanet courses given by Jan Dreier and Marcin Pilipczuk, which are scheduled for the fall 2024, will take place in the week September 9-13 at the University of Warsaw. The courses will be delivered on site only, starting at 9am on Monday September 9 and concluding in the afternoon on Friday September 13.

The registration for the Algomanet courses is now open. You can register by sending an e-mail to Jan Grebík (grebikj@mail.muni.cz) before the deadline noted below. It is possible to register for both or just one of the two courses offered. The courses are primarily intended for those affiliated with the participating universities, however, we are able to offer a limited number of places to students from other universities, too.

Registration deadline: Monday July 22, 2024
Note: We are able to accommodate a limited number of late registrations.

Jan Dreier: The combinatorics of monadic stability, monadic dependence, and related notions

Algorithmic Meta-Theorems are results that solve whole families of algorithmic problems on well-behaved classes of instances. The tractable instances are usually described using graph theory, and the families of algorithmic problems are typically described in terms of logic. In this context, we say a graph class is "tractable" if the first-order model-checking problem is FPT (fixed-parameter tractable) on this class. More precisely, a graph class C is "tractable" if there is an algorithm that decides for a given graph G from C and a sentence ɸ of first-order logic, in time f(ɸ)⋅|G|^c if ɸ holds on G (where c is a small constant independent of G and ɸ). Landmark results show that nowhere dense graph classes, hereditary stable classes, and classes of ordered graphs of bounded twin-width are tractable.

The central conjecture in the field is that for hereditary graph classes (those closed under induced subgraphs), a graph class is tractable if and only if it is "dependent". Here, "dependence" refers to a very general notion originating from model theory, where it is usually considered in the infinite. In this course, I will introduce an ongoing program that aims to prove the central conjecture by first rediscovering dependence (and related notions) as purely combinatorial, finitary, graph-theoretic concepts, and then using these concepts to develop a model-checking algorithm.

In this context, most relevant approaches were originally developed for nowhere dense graph classes, then generalized to stable graph classes, and finally extended to dependent classes. Similarly, we start this course by exploring nowhere dense classes, then stable classes, and finally dependent classes.

Marcin Pilipczuk: Parameterized algorithms for constraint satisfaction problems

Additional material: exercises, slides from the last lecture, a link to the ICALP 2024 workshop on the topic of the course

Constraint Satisfaction Problems (CSPs) is a very general language to speak about various families of computational problems. After many years of research, in 2017 the P vs NP-hard dichotomy was proven by Bulatov and Zhuk for the "most natural" case of finite languages.

Parameterized complexity is a theoretical framework that allows us to speak about running times of the algorithms in a much more refined way than just measuring it as a function of the input size. The input is measured by one or more so-called parameters, and the impact of each parameter on the running time bound is studied.

In recent years, many interesting aspects of parameterized complexity of CSPs have been explored. This includes parameterizations by the (Hamming) weight of the solution, by structural measures of the primal graph of the input instance, or by the number of satisfied or unsatisfied constraints in the optimization variants of CSPs. We will survey these developments, present main techniques and recent results.

Location and schedule

All lectures and discussion sessions will take place in the building of the Faculty of Mathematics, Informatics, and Mechanics located at ul. Stefana Banacha 2, 02-097 Warszawa. Preliminary schedule.

Monday September 9

Tuesday September 10

Wednesday September 11

Thursday September 12

Friday September 13