Model Checking on Interpretations of Classes of Bounded Local Cliquewidth

2022/02/25 by Bonnet, Édouard, Dreier, Jan, Gajarský, Jakub +4 · 1 citation
#05C85 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2202.13014

Abstract

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.

Cited by

• The S-Hamiltonian Cycle Problem

Related

• A New Perspective on FO Model Checking of Dense Graph Classes
• First-order interpretations of bounded expansion classes
• FO model checking of geometric graphs
• Merge-width and First-Order Model Checking
• Twin-width I: tractable FO model checking