Jakub Gajarský, Model Checking on Interpretations of Classes of Bounded Local Clique-Width

The first-order model checking problem for finite graphs asks, given a graph G and a first-order sentence $\phi$ as input, to decide whether $\phi$ holds on G. Showing the existence of an efficient algorithm for this problem implies the existence of efficient parameterized algorithms for various commonly studied problems, such as independent set, distance-r dominating set, and many others.

While the first-order model-checking problem is likely not efficiently solvable in general, efficient algorithms exist for various restricted graph classes, such as graphs of bounded degree, planar graphs etc. After the existence of an efficient model checking algorithm was shown for nowhere dense classes of graphs (which include most of commonly studied classes of sparse graphs), the attention turned to the more general setting of graph classes which can be obtained from sparse graphs using graph transformations called interpretations/transductions. However, despite efforts of several groups of researchers, no positive algorithmic result has been achieved since 2016, when the existence of an efficient algorithm was shown for graph classes interpretable in graphs of bounded degree.

We present a fixed-parameter tractable algorithm for first-order model checking on interpretations of graph classes with bounded local clique-width. Notably, this includes interpretations of planar graphs (and more generally, of locally bounded treewidth) and vastly generalizes the result for interpretations of graphs of bounded degree. To obtain this result we developed a new tool which works in a very general setting of dependent classes and which we believe can be an important ingredient in achieving similar results in the future.

This is joint work with Édouard Bonnet, Jan Dreier, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Toruńczyk.