Résumés

Ignasi Sau

Title:  Introduction to logic in graphs and algorithmic meta-theorems

Abstract: In this introductory talk we will define the basic concepts of logic in graphs and the relevant associated parameters, and we will provide a survey on the current landscape of algorithmic meta-theorems in graphs involving logic, some of which will be discussed in more detail in the other talks. 

Hugo Jacob 

Title: First-order model-checking on sparse graph classes

Abstract: We survey the main concepts and results on the FO-model checking on sparse graph classes and their extensions

Eunjung Kim

Title: First-order model-checking on graphs of bounded twin-width 

Abstract: Twin-width is a notion introduced by Bonnet, Kim, Thomassé and Watrigant in 2020, which was intensively studied since then. It was also proved that First-Order Model checking is fixed-parameter tractable on graphs of bounded twin-width. This generalizes known tractability result on graph classes such as planar graphs, graphs of bounded rank-width and proper interval graphs. In this talk, we give an overview of the FO model checking algorithm on graphs of bounded twin-width.

Dimitrios Thilikos

Title: Logic and algorithms for graph minors

Abstract: The Graph Minors series of Robertson and Seymour, apart from its seminal importance in modern combinatorics, offered a wealth of graph algorithmic techniques. These techniques where mainly developed for the derivation of a cubic-time algorithm for the disjoint paths problem (for fixed number of terminals) and have been extensively used for the design of parametrized graph algorithms. We present a meta-algorithmic theory that abstracts away these algorithmic techniques and make them automatically applicable to wide families of problems.

Matthieu Rosenfeld

Title: Monadic second-order logic and treewidth

Abstract: Courcelle'e theorem is the most prominent algorithmic meta-theorem and had an important impact in algorithmic graph theory. We present the main ideas of the proof of its theorem as well as its applications and its extensions in several areas of research, including autormatic theorem proving.

Giannos Stamoulis

Title: Elementary first-order model-checking

Abstract: It is known that for subgraph-closed graph classes the first-order model checking problem is fixed-parameter tractable if and only if the class is nowhere dense [Grohe, Kreutzer, Siebertz, STOC 2014]. However, the dependency on the formula size is non-elementary, and in fact, this is unavoidable even for the class of all trees [Frick and Grohe, LICS 2002]. On the other hand, it is known that the dependency is elementary for classes of bounded degree [Frick and Grohe, LICS 2002] as well as for classes of bounded pathwidth [Lampis, ICALP 2023]. In this talk, we present a recent generalization of these results and almost completely characterize subgraph-closed graph classes for which the model checking problem is fixed-parameter tractable with an elementary dependency on the formula size. Those are the graph classes for which there exists a number d such that for every r, some tree of depth d and size bounded by an elementary function of r is avoided as an (≤ r)-subdivision in all graphs in the class. In particular, this implies that if the class in question excludes a fixed tree as a topological minor, then first-order model checking for graphs in the class is fixed-parameter tractable with an elementary dependency on the formula size.