16 citations · 188 across the 122 of their papers we have counts for
17 papers · 1 filter
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…
First-order transducibility among classes of sparse graphs
Jakub Gajarský, Jeremi Gładkowski, Jan Jedelský +2
We prove several negative results about first-order transducibility for classes of sparse graphs: - for every , the class of graphs of treewidth at most is…
Low rank MSO
Mikołaj Bojańczyk, Michał Pilipczuk, Wojciech Przybyszewski +2
We introduce a new logic for describing properties of graphs, which we call low rank MSO. This is the fragment of monadic second-order logic in which set quantification is restrict…
3D-grids are not transducible from planar graphs
Jakub Gajarský, Michał Pilipczuk, Filip Pokrývka
We prove that the class of 3D-grids is cannot be transduced from planar graphs, and more generally, from any class of graphs of bounded Euler genus. To prove our result, we introdu…
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…
First-Order Model Checking on Monadically Stable Graph Classes
Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann +3
A graph class is called monadically stable if one cannot interpret, in first-order logic, arbitrary large linear orders in colored graphs from . We prove…
Flipper games for monadically stable graph classes
Jakub Gajarský, Nikolas Mählmann, Rose McCarty +6
A class of graphs is monadically stable if for any unary expansion of , one cannot interpret, in first-order logic, arbitrarily l…
Twin-width and types
Jakub Gajarský, Michał Pilipczuk, Wojciech Przybyszewski +1
We study problems connected to first-order logic in graphs of bounded twin-width. Inspired by the approach of Bonnet et al. [FOCS 2020], we introduce a robust methodology of local…
Treelike decompositions for transductions of sparse graphs
Jan Dreier, Jakub Gajarský, Sandra Kiefer +2
We give new decomposition theorems for classes of graphs that can be transduced in first-order logic from classes of sparse graphs -- more precisely, from classes of bounded expans…
Stable graphs of bounded twin-width
Jakub Gajarský, Michał Pilipczuk, Szymon Toruńczyk
We prove that every class of graphs that is monadically stable and has bounded twin-width can be transduced from some class with bounded sparse twin-width. This genera…
VC density of set systems defnable in tree-like graphs
Adam Paszke, Michał Pilipczuk
We study set systems definable in graphs using variants of logic with different expressive power. Our focus is on the notion of Vapnik-Chervonenkis density: the smallest possible d…
Model-Checking on Ordered Structures
Kord Eickmeyer, Jan van den Heuvel, Ken-ichi Kawarabayashi +6
We study the model-checking problem for first- and monadic second-order logic on finite relational structures. The problem of verifying whether a formula of these logics is true on…
Progressive Algorithms for Domination and Independence
Grzegorz Fabiański, Michał Pilipczuk, Sebastian Siebertz +1
We consider a generic algorithmic paradigm that we call progressive exploration, which can be used to develop simple and efficient parameterized graph algorithms. We identify two m…
Definable decompositions for graphs of bounded linear cliquewidth
Mikołaj Bojańczyk, Martin Grohe, Michał Pilipczuk
We prove that for every positive integer k, there exists an MSO_1-transduction that given a graph of linear cliquewidth at most k outputs, nondeterministically, some cliquewidth de…
Model-Checking for Successor-Invariant First-Order Formulas on Graph Classes of Bounded Expansion
Jan van den Heuvel, Stephan Kreutzer, Michał Pilipczuk +3
A successor-invariant first-order formula is a formula that has access to an auxiliary successor relation on a structure's universe, but the model relation is independent of the pa…
Optimizing tree decompositions in MSO
Mikołaj Bojańczyk, Michał Pilipczuk
The classic algorithm of Bodlaender and Kloks [J. Algorithms, 1996] solves the following problem in linear fixed-parameter time: given a tree decomposition of a graph of (possibly…
Definability equals recognizability for graphs of bounded treewidth
Mikołaj Bojańczyk, Michał Pilipczuk
We prove a conjecture of Courcelle, which states that a graph property is definable in MSO with modular counting predicates on graphs of constant treewidth if, and only if it is re…