5 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,…
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…
Weighted Treedepth is NP-complete on Graphs of Bounded Degree
Jona Dirks, Nicole Schirrmacher, Sebastian Siebertz +1
A treedepth decomposition of an undirected graph is a rooted forest on the vertex set of such that every edge is in ancestor-descendant relationship in …
Elimination Distance to Dominated Clusters
Nicole Schirrmacher, Sebastian Siebertz, Alexandre Vigny
In the Dominated Cluster Deletion problem, we are given an undirected graph and integers and and the question is to decide whether there exists a set of at most ver…