Sebastian Siebertz

research

∙ 08/30/2023

Data reduction for directed feedback vertex set on graphs without long induced cycles

We study reduction rules for Directed Feedback Vertex Set (DFVS) on inst...

0 Jona Dirks, et al. ∙

research

∙ 04/27/2023

On Solution Discovery via Reconfiguration

The dynamics of real-world applications and systems require efficient me...

0 Michael R. Fellows, et al. ∙

research

∙ 02/14/2023

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

Disjoint-paths logic, denoted 𝖥𝖮+𝖣𝖯, extends first-order logic (𝖥𝖮) with...

0 Nicole Schirrmacher, et al. ∙

research

∙ 02/07/2023

First-Order Model Checking on Structurally Sparse Graph Classes

A class of graphs is structurally nowhere dense if it can be constructed...

0 Jan Dreier, et al. ∙

research

∙ 01/31/2023

Flipper games for monadically stable graph classes

A class of graphs 𝒞 is monadically stable if for any unary expansion 𝒞 o...

0 Jakub Gajarsky, et al. ∙

research

∙ 09/15/2022

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

Let 𝒞 be a hereditary class of graphs. Assume that for every p there is ...

0 Samuel Braunfeld, et al. ∙

research

∙ 08/30/2022

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

Logical transductions provide a very useful tool to encode classes of st...

0 Samuel Braunfeld, et al. ∙

research

∙ 07/06/2022

Distributed domination on sparse graph classes

We show that the dominating set problem admits a constant factor approxi...

0 Ozan Heydt, et al. ∙

research

∙ 06/29/2022

Combinatorial and Algorithmic Aspects of Monadic Stability

Nowhere dense classes of graphs are classes of sparse graphs with rich s...

0 Jan Dreier, et al. ∙

research

∙ 06/28/2022

Indiscernibles and Wideness in Monadically Stable and Monadically NIP Classes

An indiscernible sequence (a̅_i)_1≤ i≤ n in a structure is an ordered se...

0 Jan Dreier, et al. ∙

research

∙ 05/02/2022

Token sliding on graphs of girth five

In the Token Sliding problem we are given a graph G and two independent ...

0 Valentin Bartier, et al. ∙

research

∙ 04/22/2022

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

A graph vertex-subset problem defines which subsets of the vertices of a...

0 Nicolas Bousquet, et al. ∙

research

∙ 03/31/2022

Transducing paths in graph classes with unbounded shrubdepth

Transductions are a general formalism for expressing transformations of ...

0 Michał Pilipczuk, et al. ∙

research

∙ 11/29/2021

Local planar domination revisited

We show how to compute a 20-approximation of a minimum dominating set in...

0 Ozan Heydt, et al. ∙

research

∙ 11/05/2021

Algorithms and data structures for first-order logic with connectivity under vertex failures

We introduce a new data structure for answering connectivity queries in ...

0 Michał Pilipczuk, et al. ∙

research

∙ 07/13/2021

First-Order Logic with Connectivity Operators

First-order logic (FO) can express many algorithmic problems on graphs, ...

0 Nicole Schrader, et al. ∙

research

∙ 05/08/2021

On set systems definable in sparse graph classes, discrepancy, and quantifier elimination

We study the (hereditary) discrepancy of definable set systems, which is...

0 Mario Grobler, et al. ∙

research

∙ 02/13/2021

Twin-width and permutations

Inspired by a width invariant defined on permutations by Guillemot and M...

0 Édouard Bonnet, et al. ∙

research

∙ 02/09/2021

Recursive Backdoors for SAT

A strong backdoor in a formula ϕ of propositional logic to a tractable c...

0 Nikolas Mählmann, et al. ∙

research

∙ 12/04/2020

Constant round distributed domination on graph classes with bounded expansion

We show that the dominating set problem admits a constant factor approxi...

0 Simeon Kublenz, et al. ∙

research

∙ 10/06/2020

Towards an arboretum of monadically stable classes of graphs

Logical transductions provide a very useful tool to encode classes of st...

0 Jaroslav Nešetřil, et al. ∙

research

∙ 07/15/2020

Rankwidth meets stability

We study two notions of being well-structured for classes of graphs that...

0 Jaroslav Nešetřil, et al. ∙

research

∙ 07/05/2020

Elimination distance to bounded degree on planar graphs

We study the graph parameter elimination distance to bounded degree, whi...

0 Alexander Lindermayr, et al. ∙

research

∙ 03/26/2020

Regular partitions of gentle graphs

Szemeredi's Regularity Lemma is a very useful tool of extremal combinato...

0 Yiting Jiang, et al. ∙

research

∙ 11/15/2019

Linear rankwidth meets stability

Classes with bounded rankwidth are MSO-transductions of trees and classe...

0 Jaroslav Nešetřil, et al. ∙

research

∙ 10/01/2019

On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets

In a reconfiguration version of an optimization problem Q the input is a...

0 Daniel Lokshtanov, et al. ∙

research

∙ 09/15/2019

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

The notion of nowhere dense graph classes was introduced by Nešetřil and...

0 Sebastian Siebertz, et al. ∙

research

∙ 09/04/2019

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

Classes with bounded rankwidth are MSO-transductions of trees and classe...

0 Jaroslav Nešetřil, et al. ∙

research

∙ 03/01/2019

Parameterized Distributed Complexity Theory: A logical approach

Parameterized complexity theory offers a framework for a refined analysi...

0 Sebastian Siebertz, et al. ∙

research

∙ 12/18/2018

Model-Checking on Ordered Structures

We study the model-checking problem for first- and monadic second-order ...

0 Kord Eickmeyer, et al. ∙

research

∙ 11/16/2018

Progressive Algorithms for Domination and Independence

We consider a generic algorithmic paradigm that we call progressive expl...

0 Grzegorz Fabiański, et al. ∙

research

∙ 10/04/2018

First-order interpretations of bounded expansion classes

The notion of bounded expansion captures uniform sparsity of graph class...

0 Jakub Gajarsky, et al. ∙

research

∙ 09/15/2018

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

For a positive integer r, a distance-r independent set in an undirected ...

0 Michał Pilipczuk, et al. ∙

research

∙ 07/10/2018

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

For p∈N, a coloring λ of the vertices of a graph G is p-centered if for ...

0 Michał Pilipczuk, et al. ∙

research

∙ 06/07/2018

Greedy domination on biclique-free graphs

The greedy algorithm for approximating dominating sets is a simple metho...

0 Sebastian Siebertz, et al. ∙

research

∙ 05/09/2018

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

We prove that for every class C of graphs with effectively bounded expan...

0 Michał Pilipczuk, et al. ∙

research

∙ 02/27/2018

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

The notions of bounded expansion and nowhere denseness not only offer ro...

0 Wojciech Nadara, et al. ∙

Sebastian Siebertz

Featured Co-authors