Prof. Dr. Sebastian Siebertz

Prof. Dr. Sebastian Siebertz

Universität Bremen
FB3: Mathematik-Informatik
Bibliothekstr. 5
28359 Bremen
Germany

Office: MZH 3160
Phone: +49 (421) 218-63751
siebertz[at]uni-bremen[dot]de

Office hours: by appointment

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

2023

2022

  • 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
  • Saeed Akhoondian Amiri, Ali Golshani, Stephan Kreutzer, Sebastian Siebertz:
    Vertex Disjoint Paths in Upward Planar Graphs. CSR 2014: 52-64
  • Martin Grohe, Stephan Kreutzer, Sebastian Siebertz:
    Deciding first-order properties of nowhere dense graphs. STOC 2014: 89-98
  • Martin Grohe, Stephan Kreutzer, Sebastian Siebertz:
    Characterisations of Nowhere Dense Graphs (Invited Talk). FSTTCS 2013: 21-40
  • Erich Grädel, Sebastian Siebertz:
    Dynamic definability. ICDT 2012: 236-248
  • Viktor Engelmann, Stephan Kreutzer, Sebastian Siebertz:
    First-Order and Monadic Second-Order Model-Checking on Ordered Structures. LICS 2012: 275-284

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.

Current PhD students and Postdocs

Dr. Alexandre Vigny

Mario Grobler

Nikolas Mählmann

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

Curriculum Vitae

PDF-Download