Sebastian Siebertz

According to our database, Sebastian Siebertz authored at least 88 papers between 2012 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Transducing paths in graph classes with unbounded shrubdepth.

Patrice Ossona de Mendez, Michal Pilipczuk, Sebastian Siebertz

Eur. J. Comb., 2025

Preface.

Daniel Král', Michal Pilipczuk, Sebastian Siebertz, Blair D. Sullivan

Eur. J. Comb., 2025

Distributed domination on sparse graph classes.

Ozan Heydt, Simeon Kublenz, Patrice Ossona de Mendez, Sebastian Siebertz, Alexandre Vigny

Eur. J. Comb., 2025

2024

Token Sliding on Graphs of Girth Five.

Valentin Bartier, Nicolas Bousquet, Jihad Hanna, Amer E. Mouawad, Sebastian Siebertz

Algorithmica, February, 2024

Twin-width and permutations.

Édouard Bonnet, Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz, Stéphan Thomassé

Log. Methods Comput. Sci., 2024

Discrepancy and sparsity.

Mario Grobler, Yiting Jiang, Patrice Ossona de Mendez, Sebastian Siebertz, Alexandre Vigny

J. Comb. Theory B, 2024

Elimination Distance to Bounded Degree on Planar Graphs Preprint.

Alexander Lindermayr, Sebastian Siebertz, Alexandre Vigny

Fundam. Informaticae, 2024

A survey on the parameterized complexity of reconfiguration problems.

Nicolas Bousquet, Amer E. Mouawad, Naomi Nishimura, Sebastian Siebertz

Comput. Sci. Rev., 2024

Kernelization Complexity of Solution Discovery Problems.

Mario Grobler, Stephanie Maaz, Amer E. Mouawad, Naomi Nishimura, Vijayaragunathan Ramamoorthi, Sebastian Siebertz

CoRR, 2024

Deterministic Parikh automata on infinite words.

Mario Grobler, Sebastian Siebertz

CoRR, 2024

Data Reduction for Directed Feedback Vertex Set on Graphs Without Long Induced Cycles.

Jona Dirks, Enna Gerhard, Mario Grobler, Amer E. Mouawad, Sebastian Siebertz

Proceedings of the SOFSEM 2024: Theory and Practice of Computer Science, 2024

Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes.

Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, Dimitrios M. Thilikos, Alexandre Vigny

Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

Solution Discovery via Reconfiguration for Problems in P.

Mario Grobler, Stephanie Maaz, Nicole Megow, Amer E. Mouawad, Vijayaragunathan Ramamoorthi, Daniel Schmand, Sebastian Siebertz

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Remarks on Parikh-Recognizable Omega-languages.

Mario Grobler, Leif Sabellek, Sebastian Siebertz

Proceedings of the 32nd EACSL Annual Conference on Computer Science Logic, 2024

2023

First-order Logic with Connectivity Operators.

Nicole Schirrmacher, Sebastian Siebertz, Alexandre Vigny

ACM Trans. Comput. Log., October, 2023

Büchi-like characterizations for Parikh-recognizable omega-languages.

Mario Grobler, Sebastian Siebertz

CoRR, 2023

Parikh Automata on Infinite Words.

Mario Grobler, Leif Sabellek, Sebastian Siebertz

CoRR, 2023

First-Order Model Checking on Structurally Sparse Graph Classes.

Jan Dreier, Nikolas Mählmann, Sebastian Siebertz

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Flipper Games for Monadically Stable Graph Classes.

Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michal Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokolowski, Szymon Torunczyk

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes.

Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, Szymon Torunczyk

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

On Solution Discovery via Reconfiguration.

Michael R. Fellows, Mario Grobler, Nicole Megow, Amer E. Mouawad, Vijayaragunathan Ramamoorthi, Frances A. Rosamond, Daniel Schmand, Sebastian Siebertz

Proceedings of the ECAI 2023 - 26th European Conference on Artificial Intelligence, September 30 - October 4, 2023, Kraków, Poland, 2023

2022

Modulo-Counting First-Order Logic on Bounded Expansion Classes.

Jarik Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz

CoRR, 2022

Decomposition horizons: from graph sparsity to model-theoretic dividing lines.

Samuel Braunfeld, Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz

CoRR, 2022

On the first-order transduction quasiorder of hereditary classes of graphs.

Samuel Braunfeld, Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz

CoRR, 2022

Indiscernibles and Wideness in Monadically Stable and Monadically NIP Classes.

Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, Szymon Torunczyk

CoRR, 2022

A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems.

Nicolas Bousquet, Amer E. Mouawad, Naomi Nishimura, Sebastian Siebertz

CoRR, 2022

On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets.

Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, Sebastian Siebertz

Algorithmica, 2022

Local Planar Domination Revisited.

Ozan Heydt, Sebastian Siebertz, Alexandre Vigny

Proceedings of the Structural Information and Communication Complexity, 2022

PACE Solver Description: GraPA-JAVA.

Moritz Bergenthal, Jona Dirks, Thorben Freese, Jakob Gahde, Enna Gerhard, Mario Grobler, Sebastian Siebertz

Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

Combinatorial and Algorithmic Aspects of Monadic Stability.

Jan Dreier, Nikolas Mählmann, Amer E. Mouawad, Sebastian Siebertz, Alexandre Vigny

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

Algorithms and Data Structures for First-Order Logic with Connectivity Under Vertex Failures.

Michal Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Szymon Torunczyk, Alexandre Vigny

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Structural Properties of the First-Order Transduction Quasiorder.

Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz

Proceedings of the 30th EACSL Annual Conference on Computer Science Logic, 2022

2021

Polynomial bounds for centered colorings on proper minor-closed graph classes.

Michal Pilipczuk, Sebastian Siebertz

J. Comb. Theory B, 2021

Kernelization and approximation of distance-r independent sets on nowhere dense graphs.

Michal Pilipczuk, Sebastian Siebertz

Eur. J. Comb., 2021

Classes of graphs with low complexity: The case of classes with bounded linear rankwidth.

Jaroslav Nesetril, Patrice Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz

Eur. J. Comb., 2021

Sparsity in Algorithms, Combinatorics and Logic (Dagstuhl Seminar 21391).

Daniel Král', Michal Pilipczuk, Sebastian Siebertz, Blair D. Sullivan

Dagstuhl Reports, 2021

First-Order Logic with Connectivity Operators.

Nicole Schrader, Sebastian Siebertz, Alexandre Vigny

CoRR, 2021

On the discrepancy of set systems definable in sparse graph classes.

Mario Grobler, Patrice Ossona de Mendez, Sebastian Siebertz, Alexandre Vigny

CoRR, 2021

Rankwidth meets stability.

Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Roman Rabinovich, Sebastian Siebertz

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Constant Round Distributed Domination on Graph Classes with Bounded Expansion.

Simeon Kublenz, Sebastian Siebertz, Alexandre Vigny

Proceedings of the Structural Information and Communication Complexity, 2021

Recursive Backdoors for SAT.

Nikolas Mählmann, Sebastian Siebertz, Alexandre Vigny

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

PACE Solver Description: PACA-JAVA.

Jona Dirks, Mario Grobler, Roman Rabinovich, Yannik Schnaubelt, Sebastian Siebertz, Maximilian Sonneborn

Proceedings of the 16th International Symposium on Parameterized and Exact Computation, 2021

2020

First-Order Interpretations of Bounded Expansion Classes.

Jakub Gajarský, Stephan Kreutzer, Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk

ACM Trans. Comput. Log., 2020

Model-Checking on Ordered Structures.

Kord Eickmeyer, Jan van den Heuvel, Ken-ichi Kawarabayashi, Stephan Kreutzer, Patrice Ossona de Mendez, Michal Pilipczuk, Daniel A. Quiroz, Roman Rabinovich, Sebastian Siebertz

ACM Trans. Comput. Log., 2020

On low rank-width colorings.

O-joung Kwon, Michal Pilipczuk, Sebastian Siebertz

Eur. J. Comb., 2020

Distributed domination on graph classes with bounded expansion.

Simeon Kublenz, Sebastian Siebertz, Alexandre Vigny

CoRR, 2020

Towards an arboretum of monadically stable classes of graphs.

Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz

CoRR, 2020

Regular partitions of gentle graphs.

Yiting Jiang, Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz

CoRR, 2020

Linear rankwidth meets stability.

Jaroslav Nesetril, Roman Rabinovich, Patrice Ossona de Mendez, Sebastian Siebertz

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Elimination Distance to Bounded Degree on Planar Graphs.

Alexander Lindermayr, Sebastian Siebertz, Alexandre Vigny

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

2019

Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes.

Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz

ACM Trans. Algorithms, 2019

Distributed Dominating Set Approximations beyond Planar Graphs.

Saeed Akhoondian Amiri, Stefan Schmid, Sebastian Siebertz

ACM Trans. Algorithms, 2019

Lossy Kernels for Connected Dominating Set on Sparse Graphs.

Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, Sebastian Siebertz

SIAM J. Discret. Math., 2019

Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness.

Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, Sebastian Siebertz

ACM J. Exp. Algorithmics, 2019

Greedy domination on biclique-free graphs.

Sebastian Siebertz

Inf. Process. Lett., 2019

Nowhere dense graph classes and algorithmic applications. A tutorial at Highlights of Logic, Games and Automata 2019.

Sebastian Siebertz

CoRR, 2019

Parameterized Distributed Complexity Theory: A logical approach.

Sebastian Siebertz

CoRR, 2019

Algorithmic Properties of Sparse Digraphs.

Stephan Kreutzer, Irene Muzi, Patrice Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Progressive Algorithms for Domination and Independence.

Grzegorz Fabianski, Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

2018

Coloring and Covering Nowhere Dense Graphs.

Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, Konstantinos S. Stavropoulos

SIAM J. Discret. Math., 2018

Parameterized circuit complexity of model checking first-order logic on sparse structures.

Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk

CoRR, 2018

Reconfiguration on Nowhere Dense Graph Classes.

Sebastian Siebertz

Electron. J. Comb., 2018

Vertex Cover Reconfiguration and Beyond.

Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Sebastian Siebertz

Algorithms, 2018

Distributed Domination on Graph Classes of Bounded Expansion.

Saeed Akhoondian Amiri, Patrice Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz

Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, 2018

On the number of types in sparse graphs.

Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

Parameterized circuit complexity of model-checking on sparse structures.

Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

2017

Deciding First-Order Properties of Nowhere Dense Graphs.

Martin Grohe, Stephan Kreutzer, Sebastian Siebertz

J. ACM, 2017

On the generalised colouring numbers of graphs that exclude a fixed minor.

Jan van den Heuvel, Patrice Ossona de Mendez, Daniel Quiroz, Roman Rabinovich, Sebastian Siebertz

Eur. J. Comb., 2017

Lossy kernels for connected distance-$r$ domination on nowhere dense graph classes.

Sebastian Siebertz

CoRR, 2017

On Wideness and Stability.

Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk

CoRR, 2017

Algorithmic Properties of Sparse Digraphs.

Stephan Kreutzer, Patrice Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz

CoRR, 2017

Structural Properties and Constant Factor-Approximation of Strong Distance-r Dominating Sets in Sparse Directed Graphs.

Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, Grischa Weberstädt

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Model-checking for successor-invariant first-order formulas on graph classes of bounded expansion.

Jan van den Heuvel, Stephan Kreutzer, Michal Pilipczuk, Daniel A. Quiroz, Roman Rabinovich, Sebastian Siebertz

Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs.

Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michal Pilipczuk, Roman Rabinovich, Sebastian Siebertz

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Nowhere dense classes of graphs (characterisations and algorithmic meta-theorems) (Nowhere Dense Klassen von Graphen) (Charakterisierungen und algorithmische Meta-Sätze)

Sebastian Siebertz

PhD thesis, 2016

A local constant factor approximation for the minimum dominating set problem on bounded genus graphs.

Saeed Akhoondian Amiri, Stefan Schmid, Sebastian Siebertz

CoRR, 2016

Kernelization and Sparseness: the Case of Dominating Set.

Pål Grønås Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, Somnath Sikdar

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

A Local Constant Factor MDS Approximation for Bounded Genus Graphs.

Saeed Akhoondian Amiri, Stefan Schmid, Sebastian Siebertz

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

The Generalised Colouring Numbers on Classes of Bounded Expansion.

Stephan Kreutzer, Michal Pilipczuk, Roman Rabinovich, Sebastian Siebertz

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015

On the generalised colouring numbers of graphs that exclude a fixed minor.

Jan van den Heuvel, Patrice Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz

Electron. Notes Discret. Math., 2015

Colouring and Covering Nowhere Dense Graphs.

Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, Konstantinos S. Stavropoulos

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2015

Graph Searching Games and Width Measures for Directed Graphs.

Saeed Akhoondian Amiri, Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

2014

Directed Width Measures and Monotonicity of Directed Graph Searching.

Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz

CoRR, 2014

Vertex Disjoint Paths in Upward Planar Graphs.

Saeed Akhoondian Amiri, Ali Golshani, Stephan Kreutzer, Sebastian Siebertz

Proceedings of the Computer Science - Theory and Applications, 2014

2013

Vertex Disjoint Path in Upward Planar Graphs.

Saeed Akhoondian Amiri, Ali Golshani, Stephan Kreutzer, Sebastian Siebertz

CoRR, 2013

Characterisations of Nowhere Dense Graphs (Invited Talk).

Martin Grohe, Stephan Kreutzer, Sebastian Siebertz

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013

2012

First-Order and Monadic Second-Order Model-Checking on Ordered Structures.

Viktor Engelmann, Stephan Kreutzer, Sebastian Siebertz

Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, 2012

Dynamic definability.

Erich Grädel, Sebastian Siebertz

Proceedings of the 15th International Conference on Database Theory, 2012