Publications: Jan Niclas Dreier

2026

Efficient reversal of transductions of sparse graph classes
Jan Dreier, Jakub Gajarský, Michał Pilipczuk
2026.
[pdf] [details]

2025

Approximate Evaluation of Quantitative Second Order Queries
Dreier, Jan, Ganian, Robert, Hamm, Thekla
2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 664-677, June 2025, IEEE Computer Society.
[pdf] [doi] [details]

Merge-Width and First-Order Model Checking
Dreier, Jan, Toruńczyk, Szymon
Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), pages 1944–1955, 2025, Association for Computing Machinery.
[pdf] [doi] [details]

2024

First-Order Model Checking on Monadically Stable Graph Classes
Dreier, Jan, Eleftheriadis, Ioannis, Mählmann, Nikolas, McCarty, Rose, Pilipczuk, Michał, Toruńczyk, Szymon
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 21-30, 2024.
[pdf] [doi] [details]

Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes
Dreier, Jan, Mählmann, Nikolas, Toru\ŉczyk, Szymon
Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 1550-1560, 2024.
[pdf] [details]

SAT backdoors: Depth beats size
Jan Dreier, Sebastian Ordyniak, Stefan Szeider
Journal of Computer and System Sciences, volume 142, pages 103520, 2024.
[doi] [details]

2023

Pseudorandom Finite Models
Jan Dreier and Jamie Tucker-Foltz
LICS, pages 1-13, 2023.
[pdf] [doi] [details]

A logic-based algorithmic meta-theorem for mim-width
Benjamin Bergougnoux, Jan Dreier, Lars Jaffke
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3282-3304, 2023.
[pdf] [doi] [details]

Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes
Jan Dreier and Nikolas Mählmann and Sebastian Siebertz and Szymon Torunczyk
50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany (Kousha Etessami and Uriel Feige and Gabriele Puppis), volume 261 of LIPIcs, pages 125:1-125:18, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond
Dreier, Jan, Mock, Daniel, Rossmanith, Peter
31st Annual European Symposium on Algorithms (ESA 2023) (Gørtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz), volume 274 of Leibniz International Proceedings in Informatics (LIPIcs), pages 43:1-43:17, 2023, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

CSP beyond tractable constraint languages
Jan Dreier and Sebastian Ordyniak and Stefan Szeider
Constraints, volume 28, number 3, pages 450-471, 2023.
[pdf] [doi] [details]

First-Order Model Checking on Structurally Sparse Graph Classes
Dreier, Jan, Mählmann, Nikolas, Siebertz, Sebastian
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 567-580, 2023, Association for Computing Machinery.
[pdf] [doi] [details]

2022

Treelike Decompositions for Transductions of Sparse Graphs
Dreier, Jan, Gajarský, Jakub, Kiefer, Sandra, Pilipczuk, Michał, Toruńczyk, Szymon
Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022), 2022, Association for Computing Machinery.
[pdf] [details]

Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
Bonnet, Édouard, Dreier, Jan, Gajarský, Jakub, Kreutzer, Stephan, Mählmann, Nikolas, Simon, Pierre, Toruńczyk, Szymon
Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2022), 2022, Association for Computing Machinery.
[pdf] [details]

Twin-width and generalized coloring numbers
Jan Dreier, Jakub Gajarský, Yiting Jiang, Patrice Ossona de Mendez, Jean-Florent Raymond
Discrete Mathematics, volume 345, number 3, pages 112746, 2022.
[pdf] [doi] [details]

Combinatorial and Algorithmic Aspects of Monadic Stability
Dreier, Jan, Mählmann, Nikolas, Mouawad, Amer E., Siebertz, Sebastian, Vigny, Alexandre
33rd International Symposium on Algorithms and Computation (ISAAC 2022) (Bae, Sang Won and Park, Heejin), volume 248 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1-11:17, 2022, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

CSP Beyond Tractable Constraint Languages
Jan Dreier, Sebastian Ordyniak, Stefan Szeider
28th International Conference on Principles and Practice of Constraint Programming, CP 2022, July 31 to August 8, 2022, Haifa, Israel (Christine Solnon), volume 235 of LIPIcs, pages 20:1-20:17, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

SAT Backdoors: Depth Beats Size
Jan Dreier and Sebastian Ordyniak and Stefan Szeider
30th Annual European Symposium on Algorithms (ESA 2022) (Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz), volume 244 of Leibniz International Proceedings in Informatics (LIPIcs), pages 46:1-46:18, 2022, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

2021

Lacon- and Shrub-Decompositions: A New Characterization of First-Order Transductions of Bounded Expansion Classes
Dreier, Jan
2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-13, 2021.
Note: distinguished paper
[doi] [details]

Approximate Evaluation of First-Order Counting Queries
Dreier, Jan, Rossmanith, Peter
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), 2021, SIAM.
[pdf] [doi] [details]

2020

Complexity of independency and cliquy trees
Katrin Casel and Jan Dreier and Henning Fernau and Moritz Gobbert and Philipp Kuinke and Fernando Sánchez Villaamil and Markus L. Schmid and Erik Jan van Leeuwen
Discr. Appl. Math., volume 272, pages 2-15, 2020.
[pdf] [doi] [details]

First-Order Model-Checking in Random Graphs and Complex Networks
Jan Dreier, Philipp Kuinke, Peter Rossmanith
28th Annual European Symposium on Algorithms (ESA 2020), volume 173 of LIPIcs, 2020, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [details]

Maximum Shallow Clique Minors in Preferential Attachment Graphs have Polylogarithmic Size
Jan Dreier, Philipp Kuinke, Peter Rossmanith
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), volume 176 of LIPIcs, 2020, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

Hard Problems on Random Graphs
Jan Dreier, Henri Lotze, Peter Rossmanith
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 40:1-40:14, 2020, Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

2019

The Complexity of Packing Edge-Disjoint Paths
Jan Dreier, Janosch Fuchs, Tim A. Hartmann, Philipp Kuinke, Peter Rossmanith, Bjoern Tauer, Hung-Lung Wang
14th International Symposium on Parameterized and Exact Computation (IPEC 2019), volume 148 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1-10:16, 2019, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[pdf] [doi] [details]

Motif Counting in Preferential Attachment Graphs
Jan Dreier and Peter Rossmanith
39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019), volume 150 of LIPIcs, pages 13:1-13:14, 2019, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[pdf] [doi] [details]

Hardness of FO Model-Checking on Random Graphs
Jan Dreier and Peter Rossmanith
14th International Symposium on Parameterized and Exact Computation (IPEC 2019), volume 148 of LIPIcs, pages 11:1-11:15, 2019, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
[doi] [details]

2018

Local Structure Theorems for Erdos-Rényi Graphs and Their Algorithmic Applications
Jan Dreier and Philipp Kuinke and Ba Le Xuan and Peter Rossmanith
44th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2018), volume 10706 of Lecture Notes in Computer Science, pages 125-136, 2018, Springer.
[pdf] [doi] [details]