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
- Jaroslav Nesetril, Patrice Ossona de Mendez, Roman Rabinovich, SebastianSiebertz:
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, SebastianSiebertz:
Rankwidth meets stability. SODA 2021: 2014-2033
- O-joung Kwon, Michal Pilipczuk, SebastianSiebertz:
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, SebastianSiebertz:
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, SebastianSiebertz, 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, SebastianSiebertz:
On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets. IPEC 2020: 24:1-24:15 - Alexander Lindermayr, SebastianSiebertz, Alexandre Vigny:
Elimination Distance to Bounded Degree on Planar Graphs. MFCS 2020: 65:1-65:12 - Jaroslav Nesetril, Roman Rabinovich, Patrice Ossona de Mendez, SebastianSiebertz:
Linear rankwidth meets stability. SODA 2020: 1180-1199
- SebastianSiebertz:
Greedy domination on biclique-free graphs. Inf. Process. Lett. 145: 64-67 (2019) - Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, SebastianSiebertz:
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, SebastianSiebertz:
Lossy Kernels for Connected Dominating Set on Sparse Graphs. SIAM J. Discret. Math. 33(3): 1743-1771 (2019) - Stephan Kreutzer, Roman Rabinovich, SebastianSiebertz:
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, SebastianSiebertz:
Distributed Dominating Set Approximations beyond Planar Graphs. ACM Trans. Algorithms 15(3): 39:1-39:18 (2019) - Michal Pilipczuk, SebastianSiebertz:
Polynomial bounds for centered colorings on proper minor-closed graph classes. SODA 2019: 1501-1520 - Grzegorz Fabianski, Michal Pilipczuk, SebastianSiebertz, Szymon Torunczyk:
Progressive Algorithms for Domination and Independence. STACS 2019: 27:1-27:16 - Stephan Kreutzer, Irene Muzi, Patrice Ossona de Mendez, Roman Rabinovich, SebastianSiebertz:
Algorithmic Properties of Sparse Digraphs. STACS 2019: 46:1-46:20
- Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, SebastianSiebertz:
Vertex Cover Reconfiguration and Beyond. Algorithms 11(2): 20 (2018) - SebastianSiebertz:
Reconfiguration on Nowhere Dense Graph Classes. Electron. J. Comb. 25(3): P3.24 (2018) - Martin Grohe, Stephan Kreutzer, Roman Rabinovich, SebastianSiebertz, 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, SebastianSiebertz, Szymon Torunczyk:
First-Order Interpretations of Bounded Expansion Classes. ICALP 2018: 126:1-126:14 - Michal Pilipczuk, SebastianSiebertz, Szymon Torunczyk:
Parameterized circuit complexity of model-checking on sparse structures. LICS 2018: 789-798 - Michal Pilipczuk, SebastianSiebertz, Szymon Torunczyk:
On the number of types in sparse graphs. LICS 2018: 799-808 - Saeed Akhoondian Amiri, Patrice Ossona de Mendez, Roman Rabinovich, SebastianSiebertz:
Distributed Domination on Graph Classes of Bounded Expansion. SPAA 2018: 143-151 - Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, SebastianSiebertz:
Lossy Kernels for Connected Dominating Set on Sparse Graphs. STACS 2018: 29:1-29:15 - Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, SebastianSiebertz:
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, SebastianSiebertz:
On the generalised colouring numbers of graphs that exclude a fixed minor. Eur. J. Comb. 66: 129-144 (2017) - Martin Grohe, Stephan Kreutzer, SebastianSiebertz:
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, SebastianSiebertz:
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, SebastianSiebertz:
Model-checking for successor-invariant first-order formulas on graph classes of bounded expansion. LICS 2017: 1-11 - Stephan Kreutzer, Roman Rabinovich, SebastianSiebertz:
Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes. SODA 2017: 1533-1545 - Stephan Kreutzer, Roman Rabinovich, SebastianSiebertz, 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, SebastianSiebertz:
On Low Rank-Width Colorings. WG 2017: 372-385
- Stephan Kreutzer, Michal Pilipczuk, Roman Rabinovich, SebastianSiebertz:
The Generalised Colouring Numbers on Classes of Bounded Expansion. MFCS 2016: 85:1-85:13 - Saeed Akhoondian Amiri, Stefan Schmid, SebastianSiebertz:
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, SebastianSiebertz, 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, SebastianSiebertz:
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, SebastianSiebertz:
Graph Searching Games and Width Measures for Directed Graphs. STACS 2015: 34-47 - Martin Grohe, Stephan Kreutzer, Roman Rabinovich, SebastianSiebertz, 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