16 papers
Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes
Ignasi Sau, Nicole Schirrmacher, Sebastian Siebertz +3
Algorithmic meta-theorems explain the tractability of large classes of computational problems by linking logical expressibility with structural graph properties. While extensions o…
Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery
Hanno von Bergen, Larissa Fastenau, Enna Gerhard +8
We study solution discovery, where the goal is to obtain a feasible solution to a problem from an initial configuration by a bounded sequence of local moves. In many applications,…
A Note on Constructive Canonical Splitter Strategies in Nowhere Dense Graph Classes
Janne Fuchser, Nikolas Mählmann, Sebastian Siebertz
The radius- splitter game is played on a graph between two players: Splitter and Connector. In each round, Connector selects a vertex , and the current game arena is rest…
On merge-models
Hector Buffière, Yuquan Lin, Jaroslav NeÅ¡et{Å}il +2
Tree-ordered weakly sparse models have recently emerged as a robust framework for representing structures in an ``almost sparse'' way, while allowing the structure to be reconstruc…
Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes
Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis +2
Disjoint-paths logic, denoted +, extends first-order logic () with atomic predicates , expressing…
The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz
A theorem of Ding, Oporowski, Oxley, and Vertigan implies that any sufficiently large twin-free graph contains a large matching, a co-matching, or a half-graph as a semi-induced su…