3 citations · 4 across the 6 of their papers we have counts for
Showing 2024Show all
2 papers · 1 filter
math.CO2024★ 1 cited
Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes
Jan Dreier, Nikolas Mählmann, Szymon Toruńczyk
A conjecture in algorithmic model theory predicts that the model-checking problem for first-order logic is fixed-parameter tractable on a hereditary graph class if and only if the…
cs.LO2024
Elementary first-order model checking for sparse graphs
Jakub Gajarský, Michał Pilipczuk, Marek Sokołowski +2
It is known that for subgraph-closed graph classes the first-order model checking problem is fixed-parameter tractable if and only if the class is nowhere dense [Grohe, Kreutzer, S…