Jakub Gajarský gave an online talk on the FO model checking on Interpretations of Classes of Bounded Local Clique-width at the Virtual Discrete Math Colloquium

On April 13, 2022, Jakub Gajarský from the University of Warsaw gave an online talk at the Virtual Discrete Math Colloquium on the FO model checking on interpretations of classes of graphs of bounded local clique-width. The title of his talk was “Model Checking on Interpretations of Classes of Bounded Local Clique-Width“.

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.

Jakub Gajarský, First-order interpretations of bounded expansion classes

The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion, defined as first-order interpretations of classes of bounded expansion. As a first step towards their algorithmic treatment, we provide their characterization analogous to the characterization of classes of bounded expansion via low treedepth decompositions, replacing treedepth by its dense analogue called shrubdepth.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.