1 citations · 3 across the 8 of their papers we have counts for
6 papers · 1 filter
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…