7 papers · 1 filter
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,…
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…
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 …
Characterizations of monadically dependent tree-ordered weakly sparse structures
Hector Buffière, Yuquan Lin, Jaroslav NeÅ¡etÅil +2
A class of structures is monadically dependent if one cannot interpret all graphs in colored expansions from the class using a fixed first-order formula. A tree-ordered -struct…
Existential Positive Transductions of Sparse Graphs
Nikolas Mählmann, Sebastian Siebertz
Monadic stability generalizes many tameness notions from structural graph theory such as planarity, bounded degree, bounded tree-width, and nowhere density. The sparsification conj…
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…