Sebastian Siebertz

Dr. Sebastian Siebertz


Research Focus & Metrics

Academic Career Length

15Years (2012-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
16 June 2017 in Journal of the ACM
Verified
Journal Article
Open access
MGMartin Grohe
Martin Grohe
SKStephan Kreutzer
Stephan Kreutzer
SSSebastian Siebertz
Sebastian Siebertz
Nowhere dense graph classes, introduced by Nešetřil and Ossona de Mendez [2010, 2011], form a large variety of classes of “sparse graphs” including the class of planar graphs, actually all classes with excluded minors, and also bounded degree graphs and graph classes of bounded expansion. We show that deciding properties of graphs definable in first-order logic is fixed-parameter tractable on nowhere dense graph classes (parameterized by the length of the input formula). At least for graph classes closed under taking subgraphs, this result is optimal: it was known before that for all classes C of graphs closed under taking subgraphs, if deciding first-order properties of graphs in C is fixed-parameter tractable, then C must be nowhere dense (under a reasonable complexity theoretic assumption). As a by-product, we give an algorithmic construction of sparse neighborhood covers for nowhere dense graphs. This extends and improves previous constructions of neighborhood covers for graph classes with excluded minors. At the same time, our construction is considerably simpler than those. Our proofs are based on a new game-theoretic characterization of nowhere dense graphs that allows for a recursive version of locality-based algorithms on these classes. On the logical side, we prove a “rank-preserving” version of Gaifman’s locality theorem.

31 May 2014
Verified
Conference Paper
Open access
PDF file
MGMartin Grohe
Martin Grohe
SKStephan Kreutzer
Stephan Kreutzer
SSSebastian Siebertz
Sebastian Siebertz

1 January 2018 in SIAM Journal on Discrete Mathematics
Verified
Journal Article
Closed access
MGMartin Grohe
Martin Grohe
SKStephan Kreutzer
Stephan Kreutzer
RRRoman Rabinovich
Roman Rabinovich
SSSebastian Siebertz
Sebastian Siebertz
KSKonstantinos Stavropoulos
Konstantinos Stavropoulos
In [M. Grohe, S. Kreutzer, and S. Siebertz, J. ACM, 64 (2017), 17] it was shown that nowhere dense classes of graphs admit sparse neighborhood covers of small degree. We show that a monotone graph class admits sparse neighborhood covers if and only if it is nowhere dense. The existence of such covers for nowhere dense classes is established through bounds on so-called weak coloring numbers. The core results of this paper are various lower and upper bounds on the weak coloring numbers and other, closely related, generalized coloring numbers. We prove tight bounds for these numbers on graphs of bounded treewidth. We clarify and tighten the relation between the density of shallow minors and the various generalized coloring numbers. These upper bounds are complemented by new, stronger exponential lower bounds on the weak and strong coloring numbers, and by superpolynomial lower bounds on the weak coloring numbers on classes of polynomial expansion. Finally, we show that computing weak $r$-coloring numbers is NP-complete for all $r\geq 3$.

5 July 2020 in ACM Transactions on Computational Logic
Verified
Journal Article
Open access
JGJakub Gajarský
Jakub Gajarský
SKStephan Kreutzer
Stephan Kreutzer
JNJaroslav NešETřil
Jaroslav NešETřil
PMPatrice Ossona De Mendez
Patrice Ossona De Mendez
MPMichał Pilipczuk
Michał Pilipczuk
STSzymon Toruńczyk
Szymon Toruńczyk
The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion , defined as first-order transductions of classes of bounded expansion. As a first step towards their algorithmic treatment, we provide their characterization analogous to the characterization of classes of bounded expansion via low treedepth covers (or colorings), replacing treedepth by its dense analogue called shrubdepth.

1 December 2017 in European Journal of Combinatorics
Verified
Journal Article
Closed access
JHJan van Den Heuvel
Jan van Den Heuvel
PMPatrice Ossona de Mendez
Patrice Ossona de Mendez
DQDaniel Quiroz
Daniel Quiroz
RRRoman Rabinovich
Roman Rabinovich
SSSebastian Siebertz
Sebastian Siebertz

1 January 2021 in European Journal of Combinatorics
Verified
Journal Article
Closed access
JNJaroslav Nešetřil
Jaroslav Nešetřil
PMPatrice Ossona de Mendez
Patrice Ossona de Mendez
RRRoman Rabinovich
Roman Rabinovich
SSSebastian Siebertz
Sebastian Siebertz