Sebastian Siebertz

Alexander Lindermayr, Sebastian Siebertz, Alexandre Vigny

We study the graph parameter elimination distance to bounded degree, which was introduced by Bulian and Dawar in their study of the parameterized complexity of the graph isomorphism problem. We prove that the problem is fixed-parameter tractable on planar graphs, that is, there exists an algorithm that given a planar graph $G$ and integers $d$ and $k$ decides in time $f(k,d)\cdot n^c$ for a computable function~$f$ and constant $c$ whether the elimination distance of $G$ to the class of degree $d$ graphs is at most $k$.

Janne Fuchser, Nikolas Mählmann, Sebastian Siebertz

The radius-$r$ splitter game is played on a graph $G$ between two players: Splitter and Connector. In each round, Connector selects a vertex $v$, and the current game arena is restricted to the radius-$r$ neighborhood of $v$. Then Splitter removes a vertex from this restricted subgraph. The game ends, and Splitter wins, when the arena becomes empty. Splitter aims to end the game as quickly as possible, while Connector tries to prolong it for as long as possible. The splitter game was introduced by Grohe, Kreutzer and Siebertz to characterize nowhere dense graph classes. They showed that a class $\mathscr{C}$ of graphs is nowhere dense if and only if for every radius $r$ there exists a number $k$ such that Splitter has a strategy on every $G\in \mathscr{C}$ to win the radius-$r$ splitter game in at most $k$ rounds. It was recently proved by Ohlmann et al. that for every nowhere dense class $\mathscr{C}$ and every radius $r$ there are only a bounded number of possible Splitter moves that are progressing, that is, moves that lead to an arena where Splitter can win in one less round. The proof of Ohlmann et al. is based on the compactness theorem and does not give a constructive bound on the number of progressing moves. In this work, we give a simple constructive proof, showing that if Splitter can force a win in the radius-$r$ game in $k$ rounds, then there are at most $(2r+1)^{\,2^{k-1}-1}$ progressing moves.

Hector Buffière, Yuquan Lin, Jaroslav Nešet{ř}il et al.

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 reconstructed through a simple first-order interpretation. A prominent example is given by twin-models, which are bounded twin-width tree-ordered weakly sparse representations of structures with bounded twin-width derived from contraction sequences. In this paper, we develop this perspective further. First, we show that twin-models can be chosen such that they preserve linear clique-width or clique-width up to a constant factor. Then, we introduce \emph{merge-models}, a natural analog of twin-models for merge-width. Merge-models represent binary relational structures by tree-ordered weakly sparse structures. The original structures can then be recovered by a fixed first-order interpretation. A merge-model can be constructed from a merge sequence. Then, its radius-$r$ merge-width will be, up to a constant factor, bounded by the radius-$r$ width of the merge sequence from which it is derived. Finally, we show that twin-models arise naturally as special cases of merge-models, and that binary structures with bounded twin-width are exactly those having a loopless merge-model with bounded radius-$r_0$ merge-width (for some sufficiently large constant $r_0$).

Ignasi Sau, Nicole Schirrmacher, Sebastian Siebertz et al.

Algorithmic meta-theorems explain the tractability of large classes of computational problems by linking logical expressibility with structural graph properties. While extensions of first-order logic such as FO+dp admit efficient model checking on graph classes excluding a fixed topological minor, comparable results for richer fragments of CMSO were previously unknown. We further develop the framework of Sau, Stamoulis, and Thilikos [SODA 2025] for fragmenting CMSO via annotated graph parameters, which restrict set quantification to vertex sets satisfying bounded structural conditions. Following this approach, we identify a fragment of CMSO, namely the one defined by allowing quantification only over sets having what we call low monodimensionality, that generalizes several previously-known logics and we show that model checking for this fragment, enhanced with the disjoint-paths predicate, is fixed-parameter tractable on topological-minor-free graph classes. Such classes essentially delimit the tractability for this logic on subgraph-closed classes. As a consequence, our results lift several known algorithmic meta-theorems beyond first-order logic to the topological-minor-free setting.

Hanno von Bergen, Larissa Fastenau, Enna Gerhard et al.

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, however, the graph that defines which vertex sets are feasible is not the same as the graph that governs how tokens, agents, or resources may move. Existing models such as token sliding and token jumping typically do not distinguish the problem graph and the movement graph. Motivated by this mismatch, we introduce a directed weighted two-graph model that cleanly separates feasibility from movement. A problem graph specifies the desired combinatorial objects, while a movement graph specifies admissible relocations and their costs. This yields a flexible framework that captures asymmetry, heterogeneous movement constraints, and weighted transitions, while subsuming classical discovery models as special cases. We investigate this model through \textsc{Path Discovery} and \textsc{Shortest Path Discovery}, where the task is to realize a vertex set containing an $s$-$t$-path or a shortest $s$-$t$-path in the problem graph. These problems are particularly natural in applications, since directed and weighted shortest paths are among the most fundamental algorithmic primitives. At the same time, previous work has already shown that discovery can be computationally hard even when the underlying optimization problem is easy. Our results show that this phenomenon persists, and becomes especially rich, in the two-graph setting. We obtain a detailed complexity picture, identifying tractable cases as well as strong hardness results.