Prof. Dr. Sebastian Siebertz
Research Interests
- Algorithmic Graph Structure Theory, in particular the theory of sparse and structurally sparse grap.
- Logic in Computer Science, in particular first-order model-checking, query evaluation, enumeration, and counting.
- Applications of stability theory in the finite.
A large part of my research is concerned with the design of efficient algorithms for graph problems. Many important problems are hard to solve in general, hence I try to identify the most general graph classes on which tractability can be achieved. I have studied intensively the theory of bounded expansion and nowhere dense graph classes, which provide a very robust notion of uniform sparsity.
I am also interested in logical methods in computer science. One of my favourite problems is the model-checking problem for first-order logic. In collaboration with Martin Grohe and Stephan Kreutzer I proved that this problem is fixed-parameter tractable on nowhere dense graph classes. I am now trying to extend this result to more general graph classes, in particular to logically defined classes as studied in classical model theory (stability theory).
Publications
2024
- Valentin Bartier, Nicolas Bousquet, Jihad Hanna, Amer E. Mouawad, Sebastian Siebertz:
Token Sliding on Graphs of Girth Five. Algorithmica 86(2): 638-655 (2024) - Alexander Lindermayr, Sebastian Siebertz, Alexandre Vigny:
Elimination Distance to Bounded Degree on Planar Graphs Preprint. Fundam. Informaticae 191(2): 129-140 (2024) - Mario Grobler, Leif Sabellek, Sebastian Siebertz:
Remarks on Parikh-Recognizable Omega-languages. CSL 2024: 31:1-31:21 - Mario Grobler, Stephanie Maaz, Nicole Megow, Amer E. Mouawad, Vijayaragunathan Ramamoorthi, Daniel Schmand, Sebastian Siebertz:
Solution Discovery via Reconfiguration for Problems in P. ICALP 2024: 76:1-76:20 - Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, Dimitrios M. Thilikos, Alexandre Vigny:
Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes. LICS 2024: 68:1-68:12 - Jona Dirks, Enna Gerhard, Mario Grobler, Amer E. Mouawad, Sebastian Siebertz:
Data Reduction for Directed Feedback Vertex Set on Graphs Without Long Induced Cycles. SOFSEM 2024: 183-197
2023
- Nicole Schirrmacher, Sebastian Siebertz, Alexandre Vigny:
First-order Logic with Connectivity Operators. ACM Trans. Comput. Log. 24(4): 30:1-30:23 (2023) - Michael R. Fellows, Mario Grobler, Nicole Megow, Amer E. Mouawad, Vijayaragunathan Ramamoorthi, Frances A. Rosamond, Daniel Schmand, Sebastian Siebertz:
On Solution Discovery via Reconfiguration. ECAI 2023: 700-707 - Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, Szymon Torunczyk:
Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes. ICALP 2023: 125:1-125:18 - Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michal Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokolowski, Szymon Torunczyk:
Flipper Games for Monadically Stable Graph Classes. ICALP 2023: 128:1-128:16 - Jan Dreier, Nikolas Mählmann, Sebastian Siebertz:
First-Order Model Checking on Structurally Sparse Graph Classes. STOC 2023: 567-580
2022
- Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, Sebastian Siebertz:
On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets. Algorithmica 84(2): 482-509 (2022) - Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz:
Structural Properties of the First-Order Transduction Quasiorder. 31:1-31:16 - Nicole Schirrmacher, Sebastian Siebertz, Alexandre Vigny:
First-Order Logic with Connectivity Operators. CSL 2022: 34:1-34:17 - Michal Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Szymon Torunczyk, Alexandre Vigny:
Algorithms and Data Structures for First-Order Logic with Connectivity Under Vertex Failures. ICALP 2022: 102:1-102:18 - Jan Dreier, Nikolas Mählmann, Amer E. Mouawad, Sebastian Siebertz, Alexandre Vigny:
Combinatorial and Algorithmic Aspects of Monadic Stability. ISAAC 2022: 11:1-11:17 - Moritz Bergenthal, Jona Dirks, Thorben Freese, Jakob Gahde, Enna Gerhard, Mario Grobler, Sebastian Siebertz:
PACE Solver Description: GraPA-JAVA. IPEC 2022: 30:1-30:4 - Ozan Heydt, Sebastian Siebertz, Alexandre Vigny:
Local Planar Domination Revisited. SIROCCO 2022: 154-173 - Valentin Bartier, Nicolas Bousquet, Jihad Hanna, Amer E. Mouawad, Sebastian Siebertz:
Token Sliding on Graphs of Girth Five. WG 2022: 56-69
- Jaroslav Nesetril, Patrice Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz:
Classes of graphs with low complexity: The case of classes with bounded linear rankwidth. Eur. J. Comb. 91: 103223 (2021) - Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Roman Rabinovich, Sebastian Siebertz:
Rankwidth meets stability. SODA 2021: 2014-2033
- O-joung Kwon, Michal Pilipczuk, Sebastian Siebertz:
On low rank-width colorings. Eur. J. Comb. 83 (2020) - Kord Eickmeyer, Jan van den Heuvel, Ken-ichi Kawarabayashi, Stephan Kreutzer, Patrice Ossona de Mendez, Michal Pilipczuk, Daniel A. Quiroz, Roman Rabinovich, Sebastian Siebertz:
Model-Checking on Ordered Structures. ACM Trans. Comput. Log. 21(2): 11:1-11:28 (2020) - Jakub Gajarský, Stephan Kreutzer, Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk:
First-Order Interpretations of Bounded Expansion Classes. ACM Trans. Comput. Log. 21(4): 29:1-29:41 (2020) - Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, Sebastian Siebertz:
On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets. IPEC 2020: 24:1-24:15 - Alexander Lindermayr, Sebastian Siebertz, Alexandre Vigny:
Elimination Distance to Bounded Degree on Planar Graphs. MFCS 2020: 65:1-65:12 - Jaroslav Nesetril, Roman Rabinovich, Patrice Ossona de Mendez, Sebastian Siebertz:
Linear rankwidth meets stability. SODA 2020: 1180-1199
- Sebastian Siebertz:
Greedy domination on biclique-free graphs. Inf. Process. Lett. 145: 64-67 (2019) - Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, Sebastian Siebertz:
Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness. ACM J. Exp. Algorithmics 24(1): 2.6:1-2.6:34 (2019) - Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, Sebastian Siebertz:
Lossy Kernels for Connected Dominating Set on Sparse Graphs. SIAM J. Discret. Math. 33(3): 1743-1771 (2019) - Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz:
Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes. ACM Trans. Algorithms 15(2): 24:1-24:19 (2019) - Saeed Akhoondian Amiri, Stefan Schmid, Sebastian Siebertz:
Distributed Dominating Set Approximations beyond Planar Graphs. ACM Trans. Algorithms 15(3): 39:1-39:18 (2019) - Michal Pilipczuk, Sebastian Siebertz:
Polynomial bounds for centered colorings on proper minor-closed graph classes. SODA 2019: 1501-1520 - Grzegorz Fabianski, Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk:
Progressive Algorithms for Domination and Independence. STACS 2019: 27:1-27:16 - Stephan Kreutzer, Irene Muzi, Patrice Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz:
Algorithmic Properties of Sparse Digraphs. STACS 2019: 46:1-46:20
- Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Sebastian Siebertz:
Vertex Cover Reconfiguration and Beyond. Algorithms 11(2): 20 (2018) - Sebastian Siebertz:
Reconfiguration on Nowhere Dense Graph Classes. Electron. J. Comb. 25(3): P3.24 (2018) - Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, Konstantinos S. Stavropoulos:
Coloring and Covering Nowhere Dense Graphs. SIAM J. Discret. Math. 32(4): 2467-2481 (2018) - Jakub Gajarský, Stephan Kreutzer, Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk:
First-Order Interpretations of Bounded Expansion Classes. ICALP 2018: 126:1-126:14 - Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk:
Parameterized circuit complexity of model-checking on sparse structures. LICS 2018: 789-798 - Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk:
On the number of types in sparse graphs. LICS 2018: 799-808 - Saeed Akhoondian Amiri, Patrice Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz:
Distributed Domination on Graph Classes of Bounded Expansion. SPAA 2018: 143-151 - Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, Sebastian Siebertz:
Lossy Kernels for Connected Dominating Set on Sparse Graphs. STACS 2018: 29:1-29:15 - Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, Sebastian Siebertz:
Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness. SEA 2018: 14:1-14:16
- Jan van den Heuvel, Patrice Ossona de Mendez, Daniel Quiroz, Roman Rabinovich, Sebastian Siebertz:
On the generalised colouring numbers of graphs that exclude a fixed minor. Eur. J. Comb. 66: 129-144 (2017) - Martin Grohe, Stephan Kreutzer, Sebastian Siebertz:
Deciding First-Order Properties of Nowhere Dense Graphs. J. ACM 64(3): 17:1-17:32 (2017) - Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michal Pilipczuk, Roman Rabinovich, Sebastian Siebertz:
Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs. ICALP 2017: 63:1-63:14 - Jan van den Heuvel, Stephan Kreutzer, Michal Pilipczuk, Daniel A. Quiroz, Roman Rabinovich, Sebastian Siebertz:
Model-checking for successor-invariant first-order formulas on graph classes of bounded expansion. LICS 2017: 1-11 - Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz:
Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes. SODA 2017: 1533-1545 - Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, Grischa Weberstädt:
Structural Properties and Constant Factor-Approximation of Strong Distance-r Dominating Sets in Sparse Directed Graphs. STACS 2017: 48:1-48:15 - O-joung Kwon, Michal Pilipczuk, Sebastian Siebertz:
On Low Rank-Width Colorings. WG 2017: 372-385
- Stephan Kreutzer, Michal Pilipczuk, Roman Rabinovich, Sebastian Siebertz:
The Generalised Colouring Numbers on Classes of Bounded Expansion. MFCS 2016: 85:1-85:13 - Saeed Akhoondian Amiri, Stefan Schmid, Sebastian Siebertz:
A Local Constant Factor MDS Approximation for Bounded Genus Graphs. PODC 2016: 227-233 - 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:
Kernelization and Sparseness: the Case of Dominating Set. STACS 2016: 31:1-31:14
- Jan van den Heuvel, Patrice Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz:
On the generalised colouring numbers of graphs that exclude a fixed minor. Electron. Notes Discret. Math. 49: 523-530 (2015) - Saeed Akhoondian Amiri, Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz:
Graph Searching Games and Width Measures for Directed Graphs. STACS 2015: 34-47 - Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, Konstantinos S. Stavropoulos:
Colouring and Covering Nowhere Dense Graphs. WG 2015: 325-338
A complete list of my publications can be found on dblp.org
Talks
- Introduction to nowhere dense graphs. CSLOG Seminar, Bremen, 14.11.2019.
- On the generalised colouring numbers. WGT-Workshop on Graph Theory and Its Applications-IX, Istanbul, 02.11.2019.
- Structural Sparsity. 29. Theorietag der Fachgruppe Automaten und Formale Sprachen, Bremen, 26.9.2019.
- Nowhere dense graph classes and algorithmic applications. Highlights of Logic, Games and Automata,
Invited tutorial, 15.9.2019.
Service
Organization of
Dagstuhl seminar Sparsity in Algorithms, Combinatorics and Logic
Program committees
- FoSSaCS 2020
- MFCS 2020
- CSL 2018
- Highlights of Logics Games and Automata 2018
- LICS 2021
- IPEC 2021
- Hightlights 2021