Model Checking on Interpretations of Classes of Bounded Local Cliquewidth

Édouard Bonnet; Jan Dreier; Jakub Gajarský; Stephan Kreutzer; Nikolas Mählmann; Pierre Simon; Szymon Torunczyk

doi:10.1145/3531130.3533367

LICS2022顶会

Model Checking on Interpretations of Classes of Bounded Local Cliquewidth

Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Torunczyk

arXiv DOI 出版方

2022年份

7被引次数

7顶会引用

摘要

We present a fixed-parameter tractable algorithm for first-order model checking on interpretations of graph classes with bounded local cliquewidth. Notably, this includes interpretations of planar graphs, and more generally, of classes of bounded genus. To obtain this result we develop 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.