37 citations · 102 across the 14 of their papers we have counts for
5 papers · 1 filter
A New Perspective on FO Model Checking of Dense Graph Classes
Jakub Gajarský, Petr Hliněný, Daniel Lokshtanov +2
We study the first-order (FO) model checking problem of dense graphs, namely those which have FO interpretations in (or are FO transductions of) some sparse graph classes. We give…
Shrub-depth: Capturing Height of Dense Graphs
Robert Ganian, Petr Hliněný, Jaroslav Nešetřil +2
The recent increase of interest in the graph invariant called tree-depth and in its applications in algorithms and logic on graphs led to a natural question: is there an analogousl…
FO Model Checking on Posets of Bounded Width
Jakub Gajarský, Petr Hliněný, Daniel Lokshtanov +4
Over the past two decades the main focus of research into first-order (FO) model checking algorithms have been sparse relational structures-culminating in the FPT-algorithm by Groh…
Faster Existential FO Model Checking on Posets
Jakub Gajarský, Petr Hliněný, Jan Obdržálek +1
We prove that the model checking problem for the existential fragment of first-order (FO) logic on partially ordered sets is fixed-parameter tractable (FPT) with respect to the for…
Lower Bounds on the Complexity of MSO1 Model-Checking
Robert Ganian, Petr Hliněný, Alexander Langer +3
One of the most important algorithmic meta-theorems is a famous result by Courcelle, which states that any graph problem definable in monadic second-order logic with edge-set quant…