1 citations · 3 across the 8 of their papers we have counts for
10 papers
Solving SAT via Treewidth Backdoors in Linear Time: Beyond Sparsity
Jan Dreier, Robert Ganian, Marlene Gründel +2
The Boolean Satisfiability (SAT) problem is a remarkably expressive computational problem, serving both as a cornerstone of complexity theory and as a unifying language for a wide…
Neighborhood Complexity and Radius-1 Merge-Width in Monadically Dependent Graph Classes
Jan Dreier, Nikolas Mählmann, Rose McCarty +2
Monadic dependence is a proposed structural dividing line for fixed-parameter tractability of first-order model checking on hereditary graph classes. A graph class is \emph{monadic…
A Rank-Preserving Locality Theorem
Jan Dreier, Szymon Toruńczyk
We prove a rank-preserving locality theorem for a syntactic variant of first-order logic, in the spirit of Gaifman's locality theorem and the rank-preserving locality theorem of Gr…
Near-Linear Time Computation of Welzl Orders on Graphs with Linear Neighborhood Complexity
Jan Dreier, Clemens Kuske
Orders with low crossing number, introduced by Welzl, are a fundamental tool in range searching and computational geometry. Recently, they have found important applications in stru…
The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz
A theorem of Ding, Oporowski, Oxley, and Vertigan implies that any sufficiently large twin-free graph contains a large matching, a co-matching, or a half-graph as a semi-induced su…
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…
Merge-width and First-Order Model Checking
Jan Dreier, Szymon Toruńczyk
We introduce merge-width, a family of graph parameters that unifies several structural graph measures, including treewidth, degeneracy, twin-width, clique-width, and generalized co…
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…
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…
Approximate Evaluation of Quantitative Second Order Queries
Jan Dreier, Robert Ganian, Thekla Hamm
Courcelle's theorem and its adaptations to cliquewidth have shaped the field of exact parameterized algorithms and are widely considered the archetype of algorithmic meta-theorems.…