Showing 2018 · cs.DMShow all
2 papers · 2 filters
cs.DM2018
First-order interpretations of bounded expansion classes
Jakub Gajarský, Stephan Kreutzer, Jaroslav Nešetřil +4
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-che…
cs.DM2018
Parameterized circuit complexity of model checking first-order logic on sparse structures
Michał Pilipczuk, Sebastian Siebertz, Szymon Toruńczyk
We prove that for every class of graphs with effectively bounded expansion, given a first-order sentence and an -element structure whose Gaifman graph belon…