1 citations · 1 across the 2 of their papers we have counts for
3 papers
cs.LO2026★ 1 cited
Efficient reversal of transductions of sparse graph classes
Jan Dreier, Jakub Gajarský, Michał Pilipczuk
(First-order) transductions are a basic notion capturing graph modifications that can be described in first-order logic. In this work, we propose an efficient algorithmic method to…
cs.DM2024
On classes of bounded tree rank, their interpretations, and efficient sparsification
Jakub Gajarský, Rose McCarty
Graph classes of bounded tree rank were introduced recently in the context of the model checking problem for first-order logic of graphs. These graph classes are a common generaliz…
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…