13 papers
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
Édouard Bonnet, Jan Dreier, Jakub Gajarský +4
We present a fixed-parameter tractable algorithm for first-order model checking on interpretations of graph classes with bounded local cliquewidth. Notably, this includes interpret…
SAT Backdoors: Depth Beats Size
Jan Dreier, Sebastian Ordyniak, Stefan Szeider
For several decades, much effort has been put into identifying classes of CNF formulas whose satisfiability can be decided in polynomial time. Classic results are the linear-time t…
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…
Twin-width and generalized coloring numbers
Jan Dreier, Jakub Gajarsky, Yiting Jiang +2
In this paper, we prove that a graph with no -subgraph and twin-width has -admissibility and -coloring numbers bounded from above by an exponential function…
Approximate Evaluation of First-Order Counting Queries
Jan Dreier, Peter Rossmanith
Kuske and Schweikardt introduced the very expressive first-order counting logic FOC(P) to model database queries with counting operations. They showed that there is an efficient mo…
First-Order Model-Checking in Random Graphs and Complex Networks
Jan Dreier, Philipp Kuinke, Peter Rossmanith
Complex networks are everywhere. They appear for example in the form of biological networks, social networks, or computer networks and have been studied extensively. Efficient algo…