6 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,…
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…
Algorithms and data structures for first-order logic with connectivity under vertex failures
Michał Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz +2
We introduce a new data structure for answering connectivity queries in undirected graphs subject to batched vertex failures. Precisely, given any graph G and integer k, we can in…
First-Order Logic with Connectivity Operators
Nicole Schirrmacher, Sebastian Siebertz, Alexandre Vigny
First-order logic (FO) can express many algorithmic problems on graphs, such as the independent set and dominating set problem, parameterized by solution size. On the other hand, F…